극적인 승리

시간 제한2초메모리 제한1024 MB

요약

상대 점수 A와 자신의 점수 B가 주어질 때, 왼손과 오른손으로 각각 노릴 과녁을 하나씩 골라 A보다 크면서 가장 낮은 총점으로 끝내야 한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 구현, 배열
정답자: 아직 제출이 없습니다

문제

주원이는 동현이와 “양손으로 공 던져서 과녁 맞추기” 경기를 하고 있다. 경기는 두 명이 번갈아 가면서 차례를 진행하며, 선수는 자신의 차례마다 양 손에 공을 하나씩 들고 각각 과녁을 향해 던진다.

과녁은 총 $N$ 개 있으며 $1$ 부터 $N$ 까지의 정수 번호가 붙어 있다. $i$ 번 과녁은 왼손으로 맞추면 $L\_i$ 점, 오른손으로 맞추면 $R\_i$ 점을 준다. 단, 과녁 하나에 두 공이 모두 맞으면 무효라서 $0$ 점이다. 경기가 끝날 때 얻은 점수의 합이 더 높은 사람이 이긴다.

시간이 지나 어느덧 주원이의 마지막 차례만 남았다. 현재 동현이는 $A$ 점, 주원이는 $B$ 점을 얻었다. 주원이는 쇼맨십을 중요시하기 때문에, 동현이를 최대한 극적으로 이기고 싶다. 즉, $A$ 점보다 높으면서 가능한 낮은 점수로 게임을 끝내고 싶다. 주원이는 이 종목의 초고수이기 때문에 왼손/오른손 각각 원하는 과녁을 무조건 맞출 수 있고, 어떤 손은 일부러 맞추지 않을 수도 있다.

주원이가 어떻게 해야 최대한 극적으로 이길 수 있는지를 구하여라. 단, 어떻게 해도 동현이보다 높은 점수를 얻으며 끝내지 못한다면 “No”를 출력한다.

입력

첫 번째 줄에 동현이의 점수 $A$ , 주원이의 점수 $B$ 가 공백으로 구분되어 주어진다.

두 번째 줄에 과녁의 개수 $N$ 이 주어진다.

세 번째 줄부터 $N$ 개의 줄에 걸쳐 과녁을 맞췄을 때 얻는 점수가 주어진다. 이 중 $i$ 번째 줄에는 $i$ 번 과녁을 왼손, 오른손으로 맞췄을 때 각각 얻는 점수인 $L\_i$ , $R\_i$ 가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 주원이가 왼손, 오른손으로 각각 노릴 과녁의 번호를 나타내는 $X$ , $Y$ 를 공백으로 구분하여 출력한다.

두 값 모두 $-1$ 이거나 $1$ 이상 $N$ 이하의 양의 정수여야 한다. 양의 정수인 경우 맞춰야 할 과녁 번호를 의미하며, $-1$ 인 경우 맞추지 않는다는 의미이다. $X=Y$ 인 경우 주원이는 0점을 얻음에 유의하라.

주원이가 어떻게 해도 동현이를 이기지 못한다면, 대신 첫 번째 줄에 “No”를 출력한다.

제한

주어지는 모든 수는 정수이다.
$0\le A,B\le 10^8$
$1\le N\le 500\\, 000$
$0\le L\_i,R\_i\le 10^8$

예제3

예제 1
입력
```
12 7
3
1 5
8 4
3 3
```
예상 출력
```
3 2
```
예제 2
입력
```
100 1
2
1 10
10 1
```
예상 출력
```
No
```
예제 3
입력
```
1 100
3
1 2
3 4
5 6
```
예상 출력
```
-1 -1
```