4회 문제풀이 04 / ABC 203 C - Friends and Travel costs
ABC 203 C - Friends and Travel costs
【문제 개요】
10¹⁰⁰ + 1개의 마을이 있으며 각각 마을0, 마을1, …, 마을10¹⁰⁰라고 번호가 붙어있습니다.
0이상 10¹⁰⁰-1이하의 모든 정수 i에 대해서, 마을 i에서 1엔을 지불하는 것으로 마을(i + 1)에 이동하는것이 가능합니다. 그것 이외의 이동 방법은 없습니다.
타로군은 처음 K엔을 가지고 있는 상태로 마을0에 있습니다. 그 후, 가능한 많은 번호의 마을을 둘러보려고 합니다.
타로군에겐 N명의 친구들이 있습니다. i명째의 친구는 마을 Aᵢ에 대해서, 타로군이 마을 Aᵢ에 도착했을때 Bᵢ엔을 타로군에게 넘겨줍니다.
타로군이 최종적으로 도착한 마을 번호를 구하시오.
【전제】
- 1 ≦ N ≦ 2 x 10⁵
- 1 ≦ K ≦ 10⁹
- 1 ≦ Aᵢ ≦ 10¹⁸
- 1 ≦ Bᵢ ≦ 10⁹
- 입력은 모두 정수이다.
【입력 형태】
1
2
3
4
N K
A₁ B₁
...
Aₙ Bₙ
【출력 형태】
답변을 출력하시오.
【예시】
입력 예 1
1
2
3
2 3
2 1
5 10
출력 예 1
1
4
타로군은 이하와 같이 움직입니다 :
- 마을 0에서 마을 1로 1엔을 지불하여 이동합니다. 소지금은 2엔입니다.
- 마을 1에서 마을 2로 1엔을 지불하여 이동합니다. 소지금은 1엔입니다.
- 마을 2에서 1번째 친구에게서 1엔을 넘겨받아 소지금이 2엔이 되었습니다.
- 마을 2에서 마을 3로 1엔을 지불하여 이동합니다. 소지금은 1엔입니다.
- 마을 3에서 마을 4로 1엔을 지불하여 이동합니다. 소지금은 0엔입니다. 따라서 4가 출력됩니다.
입력 예 2
1
2
3
4
5
6
5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
출력 예 2
1
6000000000
입력 예 3
1
2
3
4
3 2
5 5
2 1
2 2
출력 예 3
1
10
같은 마을에 친구가 여러명 있을 가능성도 있습니다.
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。