Hungry Cow

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

요약

건초 배달 날짜와 양이 주어질 때, 첫 T일 동안 소가 하루에 하나씩 먹는 건초의 총 개수를 구한다.

난이도: 보통10점 중 4점
유형: 구간, 시뮬레이션, 수학, 누적 합
정답자: 아직 제출이 없습니다

문제

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day $d\_i$ , Farmer John sends a delivery of $b\_i$ haybales ( $1\leq d\_i \leq 10^{14}$ , $1 \leq b\_i \leq 10^9$ ).

Compute the total number of haybales Bessie will eat during the first $T$ days.

입력

The first line contains $N$ and $T$ ( $1 \le N \le 10^5$ , $1 \le T \le 10^{14}$ ).

The next $N$ lines each contain $d\_i$ and $b\_i$ . It is additionally guaranteed that $1\le d\_1\<d\_2<\dots < d\_N\le T$ .

출력

Output the number of haybales that Bessie will eat during the first $T$ days.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

예제3

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