← 返回题目列表

Codeforces · 859/F

F. 订购 T 恤

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

这是另一个 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 个。