Ordering T-Shirts

题意翻译

### 题目描述 在一场比赛中，有$P$位选手参加比赛。在最后的结果中排名最靠前的$C(C \leq P)$位选手会得到由主办方赠送的一件衬衫。主办方决定在比赛开始前将必要的衬衫做好，但是他们不知道会有哪些选手成为前$C$名。 主办方已经统计好了$P$位选手希望的衬衫尺码。衬衫尺码共有$N$种，编号$1$到$N$。一些选手希望获得某一固定尺码的衬衫，而一些选手则希望获得某两个编号相邻的尺码中的一个尺码的衬衫。 现在请计算出主办方最少需要多少衬衫，使得无论哪$C$位选手最靠前，都存在一种分配方案使得所有人都能获得他想要的尺码的衬衫。 ### 输入格式 第一行两个正整数$N,C(1 \leq N \leq 2 \times 10^5 , 1 \leq C)$表示尺码数量和获得衬衫的人数； 接下来一行$2N-1$个非负数$c_1,c_2,...,c_{2N-1}(0 \leq c_i \leq 10^8)$，其中若$2 \mid i$则$c_i$表示希望获得尺码为$\frac{i}{2}$或$(\frac{i}{2} + 1)$的选手数量；否则$c_i$表示希望获得尺码$\frac{i+1}{2}$的选手数量。 设$P = \sum c_i$，则$C \leq P$。 ### 输出格式 一行一个整数表示至少要制作多少件衬衫。

题目描述

It's another Start\[c\]up, and that means there are T-shirts to order. In order to make sure T-shirts are shipped as soon as possible, we've decided that this year we're going to order all of the necessary T-shirts before the actual competition. The top $ C $ contestants are going to be awarded T-shirts, but we obviously don't know which contestants that will be. The plan is to get the T-Shirt sizes of all contestants before the actual competition, and then order enough T-shirts so that no matter who is in the top $ C $ we'll have T-shirts available in order to award them. In order to get the T-shirt sizes of the contestants, we will send out a survey. The survey will allow contestants to either specify a single desired T-shirt size, or two adjacent T-shirt sizes. If a contestant specifies two sizes, it means that they can be awarded either size. As you can probably tell, this plan could require ordering a lot of unnecessary T-shirts. We'd like your help to determine the minimum number of T-shirts we'll need to order to ensure that we'll be able to award T-shirts no matter the outcome of the competition.

输入输出格式

输入格式

Input will begin with two integers $ N $ and $ C $ ( $ 1<=N<=2·10^{5} $ , $ 1<=C $ ), the number of T-shirt sizes and number of T-shirts to be awarded, respectively. Following this is a line with $ 2·N-1 $ integers, $ s_{1} $ through $ s_{2·N-1} $ $ (0<=s_{i}<=10^{8}) $ . For odd $ i $ , $ s_{i} $ indicates the number of contestants desiring T-shirt size $ ((i+1)/2) $ . For even $ i $ , $ s_{i} $ indicates the number of contestants okay receiving either of T-shirt sizes $ (i/2) $ and $ (i/2+1) $ . $ C $ will not exceed the total number of contestants.

输出格式

Print the minimum number of T-shirts we need to buy.

输入输出样例

输入样例 #1

2 200
100 250 100

输出样例 #1

200

输入样例 #2

4 160
88 69 62 29 58 52 44

输出样例 #2

314

说明

In the first example, we can buy $ 100 $ of each size.