{"problem":{"name":"F. Ordering T-Shirts","description":{"content":"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 nece","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF859F"},"statements":[{"statement_type":"Markdown","content":"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.\n\nIn 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.\n\nAs 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.\n\n## Input\n\nInput 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.\n\nFollowing this is a line with 2·_N_ - 1 integers, _s_1 through _s_2·_N_ - 1 (0 ≤ _s__i_ ≤ 108). 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.\n\n## Output\n\nPrint the minimum number of T-shirts we need to buy.\n\n[samples]\n\n## Note\n\nIn the first example, we can buy 100 of each size.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"这是另一次 Start[c]up，意味着我们需要订购 T 恤。为了确保 T 恤能尽快发货，我们决定今年在比赛实际开始前就订购所有必需的 T 恤。前 #cf_span[C] 名参赛者将获得 T 恤，但我们显然不知道最终哪些参赛者会进入前 #cf_span[C]。我们的计划是在比赛前收集所有参赛者的 T 恤尺码，然后订购足够数量的 T 恤，以便无论谁进入前 #cf_span[C]，我们都能提供合适的 T 恤。\n\n为了获取参赛者的 T 恤尺码，我们将发放一份调查问卷。问卷允许参赛者指定一个期望的 T 恤尺码，或两个相邻的 T 恤尺码。如果参赛者指定了两个尺码，则意味着他们可以接受其中任意一个。\n\n正如你可能猜到的，这个计划可能会导致订购大量不必要的 T 恤。我们希望你能帮助我们确定，为确保无论比赛结果如何都能发放 T 恤，最少需要订购多少件 T 恤。\n\n输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[C]（#cf_span[1 ≤ N ≤ 2·105]，#cf_span[1 ≤ C]），分别表示 T 恤尺码的种类数和需要颁发的 T 恤数量。\n\n接下来一行包含 #cf_span[2·N - 1] 个整数 #cf_span[s1] 到 #cf_span[s2·N - 1]（#cf_span[0 ≤ si ≤ 108]）。对于奇数 #cf_span[i]，#cf_span[si] 表示希望获得 T 恤尺码 #cf_span[((i + 1) / 2)] 的参赛者人数；对于偶数 #cf_span[i]，#cf_span[si] 表示愿意接受 T 恤尺码 #cf_span[(i / 2)] 和 #cf_span[(i / 2 + 1)] 中任意一个的参赛者人数。#cf_span[C] 不会超过参赛者总人数。\n\n请输出我们需要购买的最少 T 恤数量。\n\n在第一个示例中，我们可以每种尺码各购买 #cf_span[100] 件。\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[C]（#cf_span[1 ≤ N ≤ 2·105]，#cf_span[1 ≤ C]），分别表示 T 恤尺码的种类数和需要颁发的 T 恤数量。接下来一行包含 #cf_span[2·N - 1] 个整数 #cf_span[s1] 到 #cf_span[s2·N - 1]（#cf_span[0 ≤ si ≤ 108]）。对于奇数 #cf_span[i]，#cf_span[si] 表示希望获得 T 恤尺码 #cf_span[((i + 1) / 2)] 的参赛者人数；对于偶数 #cf_span[i]，#cf_span[si] 表示愿意接受 T 恤尺码 #cf_span[(i / 2)] 和 #cf_span[(i / 2 + 1)] 中任意一个的参赛者人数。#cf_span[C] 不会超过参赛者总人数。\n\n## Output\n\n请输出我们需要购买的最少 T 恤数量。\n\n[samples]\n\n## Note\n\n在第一个示例中，我们可以每种尺码各购买 #cf_span[100] 件。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, C \\in \\mathbb{Z}^+ $: number of T-shirt sizes and number of T-shirts to award.  \nLet $ s_1, s_2, \\dots, s_{2N-1} \\in \\mathbb{Z}_{\\geq 0} $: survey responses, where:  \n- For odd $ i $, $ s_i $ is the number of contestants requesting size $ \\frac{i+1}{2} $ (exact size).  \n- For even $ i $, $ s_i $ is the number of contestants accepting sizes $ \\frac{i}{2} $ and $ \\frac{i}{2} + 1 $ (adjacent pair).  \n\nLet $ A = \\{a_1, a_2, \\dots, a_N\\} $ be the number of T-shirts ordered for each size $ 1 $ to $ N $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 2 \\cdot 10^5 $, $ 1 \\leq C \\leq \\sum_{i=1}^{2N-1} s_i $  \n2. For each odd $ i = 2k-1 $, $ a_k \\geq s_i $ must be satisfied in some feasible assignment.  \n3. For each even $ i = 2k $, the $ s_i $ contestants must be assignable to sizes $ k $ or $ k+1 $, i.e., the total capacity for sizes $ k $ and $ k+1 $ must cover these demands along with exact requests.  \n4. $ \\sum_{j=1}^N a_j \\geq C $, and we must be able to assign exactly $ C $ T-shirts to $ C $ contestants respecting their constraints.  \n\n**Objective**  \nMinimize $ \\sum_{j=1}^N a_j $, subject to the constraint that for **any** subset of $ C $ contestants (chosen from all respondents), there exists a valid assignment of T-shirts such that each selected contestant receives a size they accept.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF859F","tags":["greedy"],"sample_group":[["2 200\n100 250 100","200"],["4 160\n88 69 62 29 58 52 44","314"]],"created_at":"2026-03-03 11:00:39"}}