{"problem":{"name":"F. Music in Car","description":{"content":"Sasha reaches the work by car. It takes exactly _k_ minutes. On his way he listens to music. All songs in his playlist go one by one, after listening to the _i_\\-th song Sasha gets a pleasure which eq","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF746F"},"statements":[{"statement_type":"Markdown","content":"Sasha reaches the work by car. It takes exactly _k_ minutes. On his way he listens to music. All songs in his playlist go one by one, after listening to the _i_\\-th song Sasha gets a pleasure which equals _a__i_. The _i_\\-th song lasts for _t__i_ minutes.\n\nBefore the beginning of his way Sasha turns on some song _x_ and then he listens to the songs one by one: at first, the song _x_, then the song (_x_ + 1), then the song number (_x_ + 2), and so on. He listens to songs until he reaches the work or until he listens to the last song in his playlist.\n\nSasha can listen to each song to the end or _partly_.\n\nIn the second case he listens to the song for integer number of minutes, at least half of the song's length. Formally, if the length of the song equals _d_ minutes, Sasha listens to it for no less than minutes, then he immediately switches it to the next song (if there is such). For example, if the length of the song which Sasha wants to _partly_ listen to, equals 5 minutes, then he should listen to it for at least 3 minutes, if the length of the song equals 8 minutes, then he should listen to it for at least 4 minutes.\n\nIt takes no time to switch a song.\n\nSasha wants to listen _partly_ no more than _w_ songs. If the last listened song plays for less than half of its length, then Sasha doesn't get pleasure from it and that song is not included to the list of _partly_ listened songs. It is not allowed to skip songs. A pleasure from a song does not depend on the listening mode, for the _i_\\-th song this value equals _a__i_.\n\nHelp Sasha to choose such _x_ and no more than _w_ songs for _partial_ listening to get the maximum pleasure. Write a program to find the maximum pleasure Sasha can get from the listening to the songs on his way to the work.\n\n## Input\n\nThe first line contains three integers _n_, _w_ and _k_ (1 ≤ _w_ ≤ _n_ ≤ 2·105, 1 ≤ _k_ ≤ 2·109) — the number of songs in the playlist, the number of songs Sasha can listen to _partly_ and time in minutes which Sasha needs to reach work.\n\nThe second line contains _n_ positive integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 104), where _a__i_ equals the pleasure Sasha gets after listening to the _i_\\-th song.\n\nThe third line contains _n_ positive integers _t_1, _t_2, ..., _t__n_ (2 ≤ _t__i_ ≤ 104), where _t__i_ equals the length of the _i_\\-th song in minutes.\n\n## Output\n\nPrint the maximum pleasure Sasha can get after listening to the songs on the way to work.\n\n[samples]\n\n## Note\n\nIn the first example Sasha needs to start listening from the song number 2. He should listen to it _partly_ (for 4 minutes), then listen to the song number 3 to the end (for 3 minutes) and then _partly_ listen to the song number 4 (for 3 minutes). After listening to these songs Sasha will get pleasure which equals 4 + 3 + 5 = 12. Sasha will not have time to listen to the song number 5 because he will spend 4 + 3 + 3 = 10 minutes listening to songs number 2, 3 and 4 and only 1 minute is left after that.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Sasha 乘车上班，全程恰好需要 #cf_span[k] 分钟。途中他听音乐。他的播放列表中的所有歌曲按顺序播放，听完第 #cf_span[i] 首歌后，他获得的愉悦值为 #cf_span[ai]。第 #cf_span[i] 首歌的时长为 #cf_span[ti] 分钟。\\n\\n在出发前，Sasha 会选定某首歌 #cf_span[x] 开始播放，然后按顺序依次播放：首先是第 #cf_span[x] 首歌，接着是第 #cf_span[(x + 1)] 首歌，然后是第 #cf_span[(x + 2)] 首歌，依此类推。他会持续听歌，直到到达公司，或听完整个播放列表的最后一首歌为止。\\n\\nSasha 可以完整听完一首歌，也可以 _部分_ 听。\\n\\n在部分听的情况下，他必须至少听完整首歌时长的一半（以整数分钟计）。形式上，若一首歌长度为 #cf_span[d] 分钟，则他至少要听 #cf_span[\\\\lceil d/2 \\\\rceil] 分钟，然后立即切换到下一首歌（如果存在）。例如，若某首歌长度为 #cf_span[5] 分钟，则他至少要听 #cf_span[3] 分钟；若长度为 #cf_span[8] 分钟，则至少要听 #cf_span[4] 分钟。\\n\\n切换歌曲不需要时间。\\n\\nSasha 最多可以对 #cf_span[w] 首歌进行 _部分_ 听。如果最后一首被听的歌播放时间少于其时长的一半，则 Sasha 不会从中获得愉悦值，且该歌不计入 _部分_ 听的歌曲列表中。不允许跳过歌曲。一首歌的愉悦值与收听模式无关，第 #cf_span[i] 首歌的愉悦值恒为 #cf_span[ai]。\\n\\n请帮助 Sasha 选择起始歌曲 #cf_span[x] 和最多 #cf_span[w] 首歌进行部分收听，以获得最大愉悦值。编写一个程序，求出 Sasha 在上班途中能获得的最大愉悦值。\\n\\n第一行包含三个整数 #cf_span[n], #cf_span[w] 和 #cf_span[k] (#cf_span[1 ≤ w ≤ n ≤ 2·105], #cf_span[1 ≤ k ≤ 2·109]) —— 播放列表中的歌曲数量、Sasha 可以部分收听的歌曲数量上限、到达公司所需的分钟数。\\n\\n第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 104])，其中 #cf_span[ai] 表示听完第 #cf_span[i] 首歌后获得的愉悦值。\\n\\n第三行包含 #cf_span[n] 个正整数 #cf_span[t1, t2, ..., tn] (#cf_span[2 ≤ ti ≤ 104])，其中 #cf_span[ti] 表示第 #cf_span[i] 首歌的时长（分钟）。\\n\\n请输出 Sasha 在上班途中能获得的最大愉悦值。\\n\\n在第一个示例中，Sasha 应从第 #cf_span[2] 首歌开始听。他应 _部分_ 听这首歌（听 #cf_span[4] 分钟），然后完整听完第 #cf_span[3] 首歌（听 #cf_span[3] 分钟），再 _部分_ 听第 #cf_span[4] 首歌（听 #cf_span[3] 分钟）。听完这些歌后，他获得的愉悦值为 #cf_span[4 + 3 + 5 = 12]。他没有足够时间听第 #cf_span[5] 首歌，因为他听第 #cf_span[2]、#cf_span[3]、#cf_span[4] 首歌共花费 #cf_span[4 + 3 + 3 = 10] 分钟，只剩 #cf_span[1] 分钟。\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含三个整数 #cf_span[n], #cf_span[w] 和 #cf_span[k] (#cf_span[1 ≤ w ≤ n ≤ 2·105], #cf_span[1 ≤ k ≤ 2·109]) —— 播放列表中的歌曲数量、Sasha 可以部分收听的歌曲数量上限、到达公司所需的分钟数。第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 104])，其中 #cf_span[ai] 表示听完第 #cf_span[i] 首歌后获得的愉悦值。第三行包含 #cf_span[n] 个正整数 #cf_span[t1, t2, ..., tn] (#cf_span[2 ≤ ti ≤ 104])，其中 #cf_span[ti] 表示第 #cf_span[i] 首歌的时长（分钟）。\"},{\"iden\":\"output\",\"content\":\"请输出 Sasha 在上班途中能获得的最大愉悦值。 \"},{\"iden\":\"examples\",\"content\":\"输入7 2 113 4 3 5 1 4 67 7 3 6 5 3 9输出12输入8 4 205 6 4 3 7 5 4 110 12 5 12 14 8 5 8输出19输入1 1 569输出6输入1 1 347输出0\"},{\"iden\":\"note\",\"content\":\"在第一个示例中，Sasha 应从第 #cf_span[2] 首歌开始听。他应 _部分_ 听这首歌（听 #cf_span[4] 分钟），然后完整听完第 #cf_span[3] 首歌（听 #cf_span[3] 分钟），再 _部分_ 听第 #cf_span[4] 首歌（听 #cf_span[3] 分钟）。听完这些歌后，他获得的愉悦值为 #cf_span[4 + 3 + 5 = 12]。他没有足够时间听第 #cf_span[5] 首歌，因为他听第 #cf_span[2]、#cf_span[3]、#cf_span[4] 首歌共花费 #cf_span[4 + 3 + 3 = 10] 分钟，只剩 #cf_span[1] 分钟。 \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $, $ w $, $ k $ be given integers:  \n- $ n $: number of songs in the playlist,  \n- $ w $: maximum number of songs that can be listened to *partially*,  \n- $ k $: total time available (minutes to reach work).  \n\nFor each song $ i \\in \\{1, 2, \\dots, n\\} $:  \n- $ a_i \\in \\mathbb{Z}^+ $: pleasure gained from listening to song $ i $ (regardless of mode),  \n- $ t_i \\in \\mathbb{Z}^+ $, $ t_i \\geq 2 $: total length of song $ i $ in minutes.  \n\nDefine the **minimum partial listening time** for song $ i $ as:  \n$$\n\\left\\lceil \\frac{t_i}{2} \\right\\rceil\n$$\n\nDefine the **time saved** by listening to song $ i $ partially (instead of fully) as:  \n$$\ns_i = t_i - \\left\\lceil \\frac{t_i}{2} \\right\\rceil = \\left\\lfloor \\frac{t_i}{2} \\right\\rfloor\n$$\n\nSasha chooses a starting song index $ x \\in \\{1, 2, \\dots, n\\} $, and listens to songs in order: $ x, x+1, x+2, \\dots $, until either:  \n- the cumulative time reaches or exceeds $ k $, or  \n- he reaches the end of the playlist.  \n\nHe may choose to listen to **at most $ w $** songs *partially* among those he starts listening to.  \nFor any song that is listened to partially, he must listen for **at least** $ \\left\\lceil \\frac{t_i}{2} \\right\\rceil $ minutes, and **must** receive pleasure $ a_i $.  \nIf a song is listened to for **less than** $ \\left\\lceil \\frac{t_i}{2} \\right\\rceil $ minutes, it is **not counted** as listened to at all, and **no pleasure** is gained.  \nSongs are not skipped.  \n\nThe goal is to **maximize total pleasure**, subject to:  \n- total listening time $ \\leq k $,  \n- at most $ w $ songs listened to partially,  \n- songs are listened to in contiguous order starting from some $ x $,  \n- each song is either listened to fully or partially (but not skipped or partially below threshold).  \n\n---\n\n### Formal Optimization Problem:\n\nLet $ x \\in \\{1, \\dots, n\\} $ be the starting index.  \nLet $ r $ be the largest index $ \\geq x $ such that the cumulative time from song $ x $ to song $ r $, with at most $ w $ partial listens, is $ \\leq k $.  \n\nFor a fixed $ x $, define the sequence of songs $ i = x, x+1, \\dots, n $.  \nWe want to choose a subset $ P \\subseteq \\{x, x+1, \\dots, r\\} $, with $ |P| \\leq w $, such that:  \n- For each $ i \\in P $: time used = $ \\left\\lceil \\frac{t_i}{2} \\right\\rceil $,  \n- For each $ i \\notin P $: time used = $ t_i $,  \n- Total time: $ \\sum_{i=x}^{r} \\left( t_i - s_i \\cdot \\mathbb{I}_{i \\in P} \\right) \\leq k $,  \n- Total pleasure: $ \\sum_{i=x}^{r} a_i $ (all songs fully or partially listened to contribute full pleasure).  \n\nWe wish to maximize $ \\sum_{i=x}^{r} a_i $ over all valid $ x $ and subsets $ P $ of size $ \\leq w $, such that the total time $ \\leq k $.\n\n---\n\n### Equivalent Reformulation:\n\nFor a fixed starting point $ x $, let $ S = \\{x, x+1, \\dots, m\\} $ be the maximal contiguous prefix of songs starting at $ x $ that can be fully played without exceeding $ k $ minutes:  \n$$\n\\sum_{i=x}^{m} t_i \\leq k < \\sum_{i=x}^{m+1} t_i\n$$\n\nThen, we can **save** up to $ \\sum_{i \\in P} s_i $ minutes by listening to $ |P| \\leq w $ songs partially.  \nTo maximize pleasure, we want to include **as many songs as possible** in the listening list (since all contribute full pleasure), so we aim to maximize $ |S| $, subject to:  \n$$\n\\sum_{i=x}^{m} t_i - \\sum_{i \\in P} s_i \\leq k\n\\quad \\Rightarrow \\quad\n\\sum_{i \\in P} s_i \\geq \\sum_{i=x}^{m} t_i - k\n$$\n\nThus, for fixed $ x $, define:  \n- $ T_x = \\sum_{i=x}^{m} t_i $: total time if all songs are played fully,  \n- $ \\Delta_x = T_x - k $: the excess time we must save (if $ T_x > k $),  \n- We need to select a subset $ P \\subseteq \\{x, \\dots, m\\} $, $ |P| \\leq w $, such that $ \\sum_{i \\in P} s_i \\geq \\Delta_x $,  \n- If $ \\Delta_x \\leq 0 $, then no partial listening is needed, and we get full pleasure $ \\sum_{i=x}^{m} a_i $,  \n- Otherwise, we want to **minimize the number of songs** (or maximize the sum of $ a_i $) while achieving $ \\sum s_i \\geq \\Delta_x $ — but since **all songs in the contiguous segment contribute full pleasure regardless**, we just need to check whether it is **possible** to save enough time with $ \\leq w $ partial listens.\n\nThus, for each starting index $ x $, we:  \n1. Find the maximal $ m $ such that $ \\sum_{i=x}^{m} t_i \\leq k + \\sum_{\\text{max } w \\text{ savings}} $,  \n   But more efficiently:  \n2. Compute the maximal prefix length $ m $ such that $ \\sum_{i=x}^{m} t_i - \\text{max possible savings with } \\leq w \\text{ partials} \\leq k $.  \n\nBut since the pleasure is fixed for any song we include (we get $ a_i $ regardless), the problem reduces to:  \n> For each starting point $ x $, what is the **maximum number of consecutive songs** (starting at $ x $) that can be played within time $ k $, allowing up to $ w $ of them to be played partially (saving $ s_i $ minutes each), and we want to **maximize the sum of $ a_i $** over those songs.\n\nSince all songs contribute their full $ a_i $, we want to **maximize the number of songs included**, subject to time constraint with partial listening.\n\nSo for each $ x $, we want the largest $ r \\geq x $ such that:  \n$$\n\\sum_{i=x}^{r} t_i - \\max_{\\substack{P \\subseteq \\{x, \\dots, r\\} \\\\ |P| \\leq w}} \\sum_{i \\in P} s_i \\leq k\n$$\n\nWhich is equivalent to:  \n$$\n\\sum_{i=x}^{r} s_i \\geq \\sum_{i=x}^{r} t_i - k \\quad \\text{and} \\quad \\text{we can achieve this with } \\leq w \\text{ songs}\n$$\n\nBut $ \\sum_{i=x}^{r} s_i $ is the total possible savings if we partially listen to all songs in the segment. So we can use a greedy: to save the most time with at most $ w $ partial listens, we choose the $ w $ songs with the **largest** $ s_i $ in the segment.\n\nThus, for each $ x $, we can binary search on $ r $, and for each candidate $ r $, compute:  \n- Total full time: $ T = \\sum_{i=x}^{r} t_i $,  \n- Required savings: $ \\Delta = T - k $,  \n- If $ \\Delta \\leq 0 $, feasible.  \n- Else, compute the maximum possible savings from $ \\min(w, r-x+1) $ songs in $ [x, r] $, by taking the $ \\min(w, r-x+1) $ largest $ s_i $ in the segment.  \n- If that maximum savings $ \\geq \\Delta $, then feasible.\n\nThen, for each $ x $, we find the maximal $ r $ such that the above holds, and record the total pleasure $ \\sum_{i=x}^{r} a_i $.  \nThen return the maximum over all $ x $.\n\n---\n\n### Final Formal Statement:\n\nGiven:  \n- $ n, w, k \\in \\mathbb{Z}^+ $,  \n- Arrays $ a = [a_1, \\dots, a_n] $, $ t = [t_1, \\dots, t_n] $,  \n- Define $ s_i = \\left\\lfloor \\frac{t_i}{2} \\right\\rfloor $ for each $ i $.  \n\n**Objective:**  \n$$\n\\max_{x=1}^{n} \\left\\{ \\sum_{i=x}^{r_x} a_i \\ \\middle| \\ r_x = \\max\\left\\{ r \\in [x, n] \\ \\middle| \\ \\sum_{i=x}^{r} t_i - \\text{top}_{\\min(w, r-x+1)} \\left( \\{s_x, \\dots, s_r\\} \\right) \\leq k \\right\\} \\right\\}\n$$\n\nWhere $ \\text{top}_{m}(S) $ denotes the sum of the $ m $ largest elements in multiset $ S $.\n\n---\n\n### Note for Implementation:\n\nTo compute efficiently (since $ n \\leq 2 \\cdot 10^5 $), use:  \n- Two pointers (sliding window) for $ x $,  \n- A data structure (e.g., multiset or two heaps) to maintain the top $ w $ savings in the current window,  \n- Precompute prefix sums for $ t_i $ and $ a_i $,  \n- For each $ x $, extend $ r $ as far as possible, maintaining the sum of the top $ \\min(w, \\text{window size}) $ values of $ s_i $.\n\nThis yields an $ O(n \\log n) $ solution.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF746F","tags":["data structures","greedy","two pointers"],"sample_group":[["7 2 11\n3 4 3 5 1 4 6\n7 7 3 6 5 3 9","12"],["8 4 20\n5 6 4 3 7 5 4 1\n10 12 5 12 14 8 5 8","19"],["1 1 5\n6\n9","6"],["1 1 3\n4\n7","0"]],"created_at":"2026-03-03 11:00:39"}}