Hungry Cow

题目描述

Bessie 是一头饥饿的奶牛。每天晚饭时，如果牛棚里有干草捆，她就会吃掉一个干草捆。为了不让 Bessie 挨饿，农夫 John 会在某些天送来一批干草捆，这些干草捆会在早晨（晚饭之前）到达。具体来说，在第 $d_i$ 天，农夫 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"）。

1 5
1 2

2

2 5
1 2
5 10

3

2 5
1 10
5 10

5

提示

第 $1$ 天早晨送来两捆干草。Bessie 在第 $1$ 天晚饭吃掉一捆，在第 $2$ 天再吃掉一捆。第 $3 \ldots 5$ 天没有更多干草可吃。总共在前 $5$ 天吃掉 $2$ 捆干草。 第 $1$ 天早晨送来两捆干草。Bessie 在第 $1$ 天和第 $2$ 天各吃掉一捆。第 $3$ 天和第 $4$ 天没有干草可吃。第 $5$ 天早晨送来 $10$ 捆干草。Bessie 在第 $5$ 天晚饭吃掉一捆。总共在前 $5$ 天吃掉 $3$ 捆干草。 第 $1$ 天早晨送来 $10$ 捆干草。Bessie 在第 $1 \ldots 4$ 天每天吃掉一捆。第 $5$ 天早晨又送来 $10$ 捆干草，这意味着牛棚里共有 $16$ 捆干草。第 $5$ 天晚饭，Bessie 再吃掉一捆。总共在前 $5$ 天吃掉 $5$ 捆干草。 评分： 输入 4-7：$T \le 10^5$ 输入 8-13：无额外限制。 题目作者：Brandon Wang

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze