Hungry Cow

Interview

Time limit2sMemory limit1024 MB

Summary

Given haybale deliveries on specific days, count how many haybales Bessie eats in the first T days, eating one per day when stock is on hand.

Level: Easy3 of 10
Topics: Greedy, Simulation
Solved: No attempts yet

Problem

Bessie is a hungry cow. Each day, at dinner, she eats one haybale if there is one in the barn. Farmer John does not want Bessie to starve, so on some days he sends a delivery of haybales. Deliveries arrive in the morning, before dinner. Specifically, 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.

Input

The first line contains $N$ and $T$ ( $1 \le N \le 10^5$ , $1 \le T \le 10^{14}$ ). Each of the next $N$ lines contains $d_i$ and $b_i$ . It is additionally guaranteed that $1 \le d_1 < d_2 < \dots < d_N \le T$ .

Output

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

The large integers involved in this problem may require 64-bit integer types (for example, long long in C/C++).

Examples3

Example 1
Input
```
1 5
1 2
```
Expected output
```
2
```
Example 2
Input
```
2 5
1 2
5 10
```
Expected output
```
3
```
Example 3
Input
```
2 5
1 10
5 10
```
Expected output
```
5
```