Xiao Q has recently become addicted to watching short videos, often losing track of time for hours. To study the reason for Xiao Q's addiction, Xiao C has built the following model:

Xiao Q is preparing to watch short videos for an expected duration of $T$ seconds. There are $n$ short videos cached on Xiao Q's phone, where the $i$-th video has a duration of $t_i$ seconds and an appeal value of $k_i$ to Xiao Q.

Xiao Q will browse all $n$ short videos in order of their index, and switching between videos takes no time. At the end of each second, Xiao Q will consider whether to stop watching:

• If all $n$ short videos have finished playing, Xiao Q will stop watching.
• Otherwise, if the current cumulative viewing time does not exceed $T$ seconds, Xiao Q will continue to watch the videos normally.
• Otherwise, suppose the total time watched so far is $x$ seconds ($x > T$): if the appeal of the current video is less than $x - T$, Xiao Q will stop watching this specific video. If this is the last video, Xiao Q will stop watching altogether; otherwise, Xiao Q will start watching the next video. Note that regardless of the appeal of the next video, Xiao Q will only make a decision again at the end of the next second.

Given the information about the cached videos, can you help Xiao C calculate the total number of seconds Xiao Q will spend watching short videos?

Input

The first line contains two positive integers $n, T$ ($1 \le n \le 10^5, 1 \le T \le 10^9$), representing the number of short videos and the duration Xiao Q plans to watch, respectively.

The next $n$ lines each contain two integers $t_i, k_i$ ($1 \le t_i, k_i \le 10^9$), representing the duration and the appeal of the $i$-th cached video.

Output

Output a single integer representing the total number of seconds Xiao Q spends watching short videos.

Examples

Input 1

3 5
1 2
2 3
3 4

Output 1

6

Input 2

3 1
1 1
2 2
3 3

Output 2

5