《技术》学考及选考相关问题请联系张博士13958083702(手机和微信同号) 问题 6192 --Bessie吃晚餐

6192: Bessie吃晚餐★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 5  解决: 5
[提交][状态][命题人:]

题目描述

Bessie是一头饥饿的牛。每天晚餐时,如果谷仓里有干草包,她会吃一个干草包。农夫约翰不想让Bessie挨饿,所以他会寄来干草包的天,这些干草包在早上到达(晚餐之前)。即在di天,农夫约翰发送了bi干草包 (1≤di≤1e14,1≤bi≤1e9).

请计算Bessie在T天吃的干草包总数。


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 di, Farmer John sends a delivery of bi haybales (1≤di≤1014, 1≤bi≤109).

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


输入

第一行包含N和T(1≤N≤1e5,1≤T≤1e14).
接下来N行,每行包含di和bi.

测试数据保证1≤d1<d2<⋯<dN≤T.

The first line contains N and T (1≤N≤1051≤T≤1014).

The next N lines each contain di and bi. It is additionally guaranteed that 1≤d1<d2<⋯<dN≤T.


输出

输出 Bessie 在T天吃掉的干草包总量。

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

样例输入
Copy
1 5
1 2
样例输出
Copy
2

提示

测试样例2
示例输入:
2 5
1 2
5 10
示例输出:
3

测试样例3
示例输入:
2 5
1 10
5 10
示例输出:
5

在测试样例1中,当天早上有两捆干草包到达.Bessie当天晚餐吃了一个干草包,另一个干草包第2天晚餐吃。在第3..5日没干草包吃。5天中,Bessie共吃了2个干草包 。
在测试样例2中,第1天早上有两捆干草到达.Bessie在第1天、第2天各吃一个干草包.第3、4天没有干草包吃。第5天的早晨到了10个干草包,Bessie当天吃了1个干草作为晚餐。5天中,Bessie共吃了3个干草包 。
在测试样例3中,干草包在第1天早上到了10个干草包.Bessie在1..4天每天各吃一个干草包。第5天的早晨到了10个干草包,Bessie当天吃了1个干草作为晚餐。5天中,Bessie共吃了5个干草包。

来源

[提交][状态]

如有问题,请咨询客服
浙ICP备20001167号