문제
태현이는 지난달에 격투기 챔피언이 되었다.
태현이는 1년마다 랭킹이 가장 높은 상대와 지명 방어전을 치러야 한다.
그 이전에 태현이는 랭킹에 있는 M명의 선수 중 한명씩을 지명해서 최대 N번의 방어전을 원하는 상대와 치를 수 있다.
랭킹에 있는 선수들의 인기도에 따라서 태현이가 승리할 경우 받게되는 파이트머니(대전료)가 각각 다르게 책정되어 있다.
태현이는 경기에서 이길 경우에는 물론 무승부를 하더라도 챔피언 타이틀을 유지하면서 대전료를 받을 수 있다.
태현이는 N번 이내의 경기를 통해 가능한 많은 돈을 벌고 싶어 한다.
당연히 이길 수 있는 상대 중 파이트머니를 많이 받을 수 있는 상대를 골라서 방어전을 치르는 것이 유리하다.
태현이는 매니저에게 부탁해 그동안 경기들을 모두 종합하여 랭킹에 있는 모든 선수들의 실력 레벨을 정수로 표시했다.
태현이보다 실력이 낮거나 같은 상대를 골라서 경기를 하면 챔피언 타이틀을 지키면서 대전료를 챙길 수 있다.
태현이는 챔피언 타이틀을 유지하면서 최소한 K원 이상의 돈을 벌고 싶다.
훈련 계획을 세우기 위해서 태현이의 실력 레벨이 최소 얼마 이상 되어야 하는지를 알아내야 한다.
태현이가 훈련에 전념할 수 있도록 K원 이상의 돈을 벌기 위해 유지해야 하는 최소 실력 레벨을 구하는 프로그램을 작성해 주도록 하자.
입력
첫 번째 줄에 경기를 치를 수 있는 최대 횟수 N (1 ≤ N ≤ 200,000) 과,
벌어야 하는 돈의 최소 금액 K (1 ≤ K < 2 * 109),
랭킹에 있는 선수들의 수 M (N ≤ M ≤ 200,000) 이 주어진다.
다음 M개의 줄에는 1번부터 M번 선수의 인기도(받을 수 있는 파이트머니) fi (0 ≤ fi ≤ 10,000) 와,
실력 레벨 li (1 ≤ li < 2 * 109) 가 공백을 사이에 두고 주어진다. (fi, li는 정수)
출력
첫 번째 줄에 타이틀을 유지하면서 K원의 돈을 벌기 위해 필요한 최소 실력 레벨을 출력한다.
만약 아무리 실력 레벨을 올려도 K원을 벌 수 없으면 첫 번째 줄에 –1 을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 6점 | N = 1 |
| #2 | 11점 | M <= 10 |
| #3 | 33점 | li <= 100 |
| #4 | 50점 | 추가 제한 조건 없음 |
예제 #1
3 10 5
3 4
4 5
5 7
3 3
1 2
5
예제 #2
3 10 5
3 4
4 5
5 7
3 3
10 2
2
예제 #3
3 10 5
3 4
2 5
3 7
2 3
3 2
-1
로그인해야 코드를 작성할 수 있어요.