Informatica Online Judge

  점수 조작 #2 [2261 / 08D5]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 5   Total Tried : 6


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[35th 김세빈]
Writer ID : [gs17018]

Background

경곽의 유서 깊은 정보과학 학술동아리 IamCoder의 선발 시험은 총 이틀에 걸쳐 이루어진다. 응시자들의 최총 점수는 1일차 점수와 2일차 점수를 합산하여 매겨지는데, 정확하게는 (1일차 점수) * p + (2일차 점수) * q로 정해진다. 이때 p와 q는 합이 어떤 짝수 T로 고정된 음이 아닌 정수이다. p와 q의 값은 선발 과정이 모두 끝날 때까지는 공개되지 않는다.

선발 시험에는 총 N명의 신입생들이 응시하였고, 기장 교준이는 이들을 최종 점수에 따라 내림차순으로 정렬한 뒤 상위 K명을 선발하려고 한다. 이때 K번째 학생과 최종 점수가 같은 사람이 더 있는 경우(동점자들이 커트라인에 걸칠 경우) 모두 선발하기로 하였다. 즉 어떤 학생이 선발되기 위한 조건은 "그 학생보다 최종 점수가 큰 사람이 K명 미만"인 것이다.

IamCoder 선발 시험을 본 신입생 고준이는 p와 q의 정확한 값은 알지 못하지만, 만약 p = q일 경우 자신이 꼴등이 된다는 사실을 알고 충격에 빠졌다. 어떻게든 IamCoder에 들어가고 싶었던 고준이는 기장 교준이를 매수하였다.

IamCoder 선발 과정은 투명(?)하여 모든 응시자들의 1일차 점수와 2일차 점수가 이미 공개되었기 때문에, 이를 수정하는 것은 불가능하다. 대신 교준이는 아직 공개하지 않은 p와 q의 값을 적당히 변경하여 최종 점수를 조작하기로 하였다. 이때 p와 q의 차이가 너무 크면 의심을 받을 수 있으므로, p와 q의 차를 최소화하려고 한다.

고준이가 선발될 수 있도록 하면서, |p-q|의 값을 최소로 하는 p와 q를 구하는 프로그램을 작성하시오. 만약 조건을 만족하는 p와 q가 둘 이상 존재한다면, p가 가장 작은 쌍을 구하면 된다.

Input

첫 번째 줄에 정수 N, K, T가 주어진다.
두 번째 줄부터 N+1번째 줄까지, i+1번째 줄에 두 개의 정수 A_i와 B_i가 주어진다. 이들은 각각 i번 학생의 1일차 점수와 2일차 점수를 의미한다. 고준이는 1번 학생이다.

모든 입력 데이터는 아래의 조건을 만족한다 :

2 <= N <= 3*10^5
1 <= K < N
2 <= T <= 10^9, T는 짝수
1 <= i <= N을 만족하는 i에 대해, 0 <= A_i, B_i <= 10^9
2 <= i <= N을 만족하는 i에 대해, A_1 + B_1 <= A_i + B_i

Output

조건을 만족하는 p와 q가 존재한다면, 첫째 줄에 두 개의 정수 p와 q를 출력한다.
조건을 만족하는 p와 q가 존재하지 않는다면, 첫째 줄에 -1을 출력한다.

IO Example

Input 1

5 3 16
3 5
2 7
5 4
4 5
1 8

Output 1

11 5

Input 2

4 2 18
1 1
2 1
1 2
2 2

Output 2

-1

Note

첫 번째 예제에서, p = 11, q = 5일 때 각 학생의 최종 점수는 아래와 같다.
1번 : 3 * 11 + 5 * 5 = 58
2번 : 2 * 11 + 7 * 5 = 57
3번 : 5 * 11 + 4 * 5 = 75
4번 : 4 * 11 + 5 * 5 = 69
5번 : 1 * 11 + 5 * 8 = 51
따라서 1번 학생인 고준이는 3번, 4번 학생에 이어 3등을 차지할 수 있다.

두 번째 예제에서, p와 q가 어떠한 값을 갖더라도 고준이보다 최종 점수가 큰 사람이 2명 이상 존재한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]