这是另一个 Start[c]up,这意味着有 T 恤可供订购。为了确保T恤尽快发货,我们决定今年在正式比赛之前订购所有必需的T恤。排名前C的选手将获得T恤,但我们显然不知道会是哪些选手。我们的计划是在正式比赛之前获取所有参赛者的 T 恤尺寸,然后订购足够的 T 恤,以便无论谁进入前 C,我们都会有 T 恤来奖励他们。
为了获得参赛者的T恤尺寸,我们将发出一份调查问卷。该调查将允许参赛者指定一个所需的 T 恤尺码,或两个相邻的 T 恤尺码。如果参赛者指定了两种尺寸,则意味着他们可以获得任一尺寸。
正如您可能知道的那样,此计划可能需要订购大量不必要的 T 恤。我们希望您帮助确定我们需要订购的 T 恤的最低数量,以确保无论比赛结果如何,我们都能够颁发 T 恤。
输入
输入将以两个整数 N 和 C (1 ≤ N ≤ 2·105, 1 ≤ C) 开始,分别是要奖励的 T 恤尺寸数量和 T 恤数量。
接下来是一行包含 2·N - 1 个整数,s1 到 s2·N - 1 (0 ≤ si ≤ 108)。对于奇数 i,si 表示想要 T 恤尺寸的参赛者数量 ((i + 1) / 2)。对于偶数 i,si 表示可以接受 T 恤尺寸 (i / 2) 和 (i / 2 + 1) 之一的参赛者数量。 C 不超过参赛者总数。
输出
打印出我们需要购买的最少 T 恤数量。
示例
输入 #1
2 200 100 250 100
输出 #1
200
输入 #2
4 160 88 69 62 29 58 52 44
输出 #2
314
注意
在第一个示例中,我们可以购买每种尺寸 100 个。