독서 모임의 책 한 권

문제

도서관의 독서 모임에서는 다음 모임까지 함께 읽을 책 한 권을 고르려 한다. 참여자들은 일정 분량 이상을 읽고 싶어 하지만, 너무 두꺼운 책을 고르면 정해진 기간 안에 읽기 어렵다. 사서는 대출 가능한 후보 목록을 받아 모임에서 정한 기준에 가장 잘 맞는 책을 선택하려 한다. 후보 목록에는 N권의 책이 있으며, 목록에 적힌 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 책의 본문 분량은 P_i쪽이다. 모임에서 정한 최소 독서 분량은 M쪽이므로, 본문 분량이 M쪽 이상인 책만 선택할 수 있다. 본문 분량이 정확히 M쪽인 책도 선택할 수 있으며, M쪽보다 적은 책은 다른 조건과 관계없이 후보에서 제외한다. 선택할 수 있는 책이 여러 권이면 최소 독서 분량을 넘겨 읽어야 하는 쪽수가 가장 적은 책을 고른다. 즉, 선택 가능한 책 중 P_i - M이 가장 작은 책을 선택한다. 초과 분량이 같은 책이 여러 권이면 목록에서 먼저 나온 책, 곧 번호가 가장 작은 책을 선택한다. 서로 다른 번호에 같은 분량이 적혀 있어도 각 번호는 별개의 책을 나타낸다. 이 모임에서는 반드시 책 한 권만 선택한다. 여러 책의 분량을 합쳐 최소 독서 분량을 채우거나, 한 책의 일부만 읽는 방식은 허용하지 않는다. 또한 후보 목록의 순서에는 분량에 따른 정렬 규칙이 없으므로, 뒤에 있는 책이 앞에 있는 책보다 얇을 수도 있다. 모든 후보의 분량을 확인하여 위 기준에 따라 책을 고르고, 선택한 책의 번호와 초과 분량을 출력한다. 어느 책도 최소 독서 분량을 충족하지 못하면 선택할 수 있는 책이 없다는 값을 출력한다.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 50,000, 1 ≤ M ≤ 100,000이다.
둘째 줄에 정수 P_1, P_2, ..., P_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ P_i ≤ 100,000이다.

출력

선택할 수 있는 책이 있으면 선택한 책의 번호와 초과 분량 P_i - M을 공백으로 구분하여 출력한다. 초과 분량이 최소인 책을 선택하고, 동점이면 번호가 가장 작은 책을 선택한다. 선택할 수 있는 책이 없으면 -1만 출력한다.

6 180
170 220 190 180 180 205

4 0

4 100
130 90 130 150

1 30

3 300
120 299 250

-1

출처: Devin.KR 자체 제작