Ordering T-Shirts
Contest: MemSQL Start[c]UP 3.0 - Round 1
Difficulty rating: 2800
Tags: greedy

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 format:
Input will begin with two integers N and C (1 ≤ N ≤ 2·105, 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, s1 through s2·N - 1 (0 ≤ si ≤ 108). For odd i, si indicates the number of contestants desiring T-shirt size ((i + 1) / 2). For even i, si 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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
2 200
100 250 100

Example output:
200

Example input:
4 160
88 69 62 29 58 52 44

Example output:
314

Editorial:
Let us first describe how to tell if a given set of T-shirts is sufficient to award the competitors. For any set of T-shirt sizes, it clearly must be the case that the total number of T-shirts ordered of sizes in the set must be at least as large as the maximum number of competitors that could require a T-shirt size from the set. We claim that this is sufficient as well, and will prove it using the max-flow min-cut theorem.
Construct a flow graph with a source, one node for each type of survey response, one node for each T-shirt size, and a sink. Add an edge from the source to each survey response node with capacity equal to the number of winners with that response. Add an edge from each survey response to the corresponding T-shirt size(s) with unlimited capacity. Add an edge from each T-shirt size to the sink with capacity equal to the number of T-shirts ordered. Find a minimum cut in this graph. Then for any maximal contiguous range of T-shirt sizes in the cut, we can remove those T-shirt sizes from the cut and instead cut the corresponding survey responses. It follows that the cut consisting only of survey responses is minimal, and by the max-flow min-cut theorem, an assignment exists that awards all winners T-shirts.
Note that we don't need to consider all sets of T-shirt sizes - only contiguous sets of T-shirts sizes are relevant. If a non-contiguous set of T-shirt sizes violates the constraint, then one of its contiguous subsections must also violate the constraint.
In other words, if we order ti shirts of size i, we only need to satisfy $$t_i + \ldots + t_j \geq \min(c, s_{2i-1} + \ldots + s_{2j-1}), \forall 1 \leq i \leq j \leq n$$.
We now will show that the algorithm that greedily orders as few of each T-shirt as possible, starting from the smallest size, produces an optimal result. Suppose, to the contrary, that a better solution exists, and consider the lexicographically smallest such solution. At the first point where the solutions differ, the optimal solution must order more T-shirts (due to the greedy nature of the algorithm). If we change the optimal solution by ordering one fewer of that size and one more of the next size up, the solution will remain valid. However this violates the lexicographical minimality of the solution, a contradiction.
Our solution is for each index j from 1 to n, to set $$t_j = \max_{1 \leq i \leq j} (\min(c, s_{2i-1} + \ldots + s_{2j-1}) - (t_i + \ldots + t_{j-1}))$$. This can easily be done in O(n2) time if we compute cumulative sums of t and s.
In order to solve it faster, we need to be able to quickly find the index i that maximizes the above expression. First lets consider the indexes where c < s2i - 1 + ... + s2j - 1. Because all t terms are non-negative, we only need to consider the largest such i for which this is true, which can be found in amortized constant time.
Now consider indexes where c ≥ s2i - 1 + ... + s2j - 1. Denote r[i][j] = (s2i - 1 + ... + s2j - 1) - (ti + ... + tj - 1). Notice that for indexes i1, i2 < j, we have r[i1][j] - r[i2][j] = r[i1][j - 1] - r[i2][j - 1]. This implies that if r[i1][j] > r[i2][j] for some index j, it is true for all valid indexes j. Create a list of indexes l maintaining invariants $$l[a] < l[b] \land r[l[a][j]] > r[l[b][j]] \forall a < b$$. Delete entries from the front of l whenever they no longer satisfy c ≥ s2i - 1 + ... + s2j - 1. Insert j at the end of the list on every iteration, deleting other indexes from the back of the list as necessary in order to maintain the invariants. At each step, the index that maximizes r[i][j] can be found at the front of the list. Using a doubly-ended queue for l makes all of these operations amortized constant time, for a total runtime of O(n).