← 返回题目列表

Codeforces · 499/A

A. 看电影

中文机器翻译题面 查看原题

您决定观看某部电影的精彩瞬间。您的播放器上有两个按钮:

1. 观看电影的当前分钟。通过按此按钮,您可以观看电影的当前分钟,并且播放器会自动前进到电影的下一分钟。
2. 正好跳过电影的 x 分钟(x 是某个固定正整数)。如果播放器现在处于电影的第 t 分钟,则按下此按钮后,将继续播放到分钟 (t + x)。

最初,电影在第一分钟在播放器中打开,并且您想要观看电影的 n 个最佳时刻,第 i 个最佳时刻从第 li 分钟开始,在第 ri 分钟结束(更正式地说,第 i 个最佳时刻由分钟组成:li, li + 1, ..., ri)。

确定一下,如果你想观看所有精彩瞬间,你必须观看的电影最少需要多少分钟?

输入

第一行包含两个以空格分隔的整数 n, x (1 ≤ n ≤ 50, 1 ≤ x ≤ 105) — 电影最佳时刻的数量以及第二个按钮的 x 值。

接下来的n行包含了电影精彩瞬间的描述,描述的第i行包含了两个用空格分隔的整数li,ri (1 ≤ li ≤ ri ≤ 105)。

保证对于从 2 到 n 的所有整数 i,以下条件成立:ri - 1 < li。

输出

输出一个数字——问题的答案。

示例

输入 #1

2 3
5 6
10 12

输出 #1

6

输入 #2

1 1
1 100000

输出 #2

100000

注意

在第一个示例中,玩家最初在第一分钟站立。由于从第一分钟到第四分钟不包含有趣的时刻,因此我们按下第二个按钮。现在我们不能按第二个按钮再跳过 3 分钟,因为其中一些包含有趣的时刻。因此,我们从第4分钟观看电影到第6分钟,之后当前时间为7。同样,我们再次跳过3分钟,然后从电影的第10分钟观看到第12分钟。我们总共看了6分钟的电影。

在第二个示例中,电影非常有趣,因此您必须观看电影的全部 100000 分钟。