배고픈 소

면접 대비

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

요약

날짜별 건초 배달이 주어질 때, 베시가 처음 T일 동안 먹는 건초의 총 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

배고픈 소 Bessie는 매일 저녁 식사 때 외양간에 건초 더미가 있으면 하나를 먹는다. Farmer John은 Bessie가 굶지 않도록 가끔 건초를 배달한다. 배달된 건초는 저녁 식사 전 아침에 도착한다. 구체적으로 $d_i$ 일에 Farmer John은 $b_i$ 개의 건초 더미를 보낸다 ( $1 \leq d_i \leq 10^{14}$ , $1 \leq b_i \leq 10^9$ ).

처음 $T$ 일 동안 Bessie가 먹는 건초 더미의 총개수를 구하라.

입력

첫째 줄에 $N$ 과 $T$ 가 주어진다 ( $1 \le N \le 10^5$ , $1 \le T \le 10^{14}$ ). 다음 $N$ 개의 줄에는 각각 $d_i$ 와 $b_i$ 가 주어진다. 또한 $1 \le d_1 < d_2 < \dots < d_N \le T$ 가 보장된다.

출력

처음 $T$ 일 동안 Bessie가 먹는 건초 더미의 개수를 출력한다.

이 문제는 큰 정수를 다루므로 64비트 정수 자료형(C/C++의 long long 등)을 사용해야 할 수도 있다.

예제3

예제 1
입력
```
1 5
1 2
```
예상 출력
```
2
```
예제 2
입력
```
2 5
1 2
5 10
```
예상 출력
```
3
```
예제 3
입력
```
2 5
1 10
5 10
```
예상 출력
```
5
```