{"raw_statement":[{"iden":"statement","content":"Polycarp takes part in a math show. He is given _n_ tasks, each consists of _k_ subtasks, numbered 1 through _k_. It takes him _t__j_ minutes to solve the _j_\\-th subtask of any task. Thus, time required to solve a subtask depends only on its index, but not on the task itself. Polycarp can solve subtasks in any order.\n\nBy solving subtask of arbitrary problem he earns one point. Thus, the number of points for task is equal to the number of solved subtasks in it. Moreover, if Polycarp _completely_ solves the task (solves all _k_ of its subtasks), he recieves one extra point. Thus, total number of points he recieves for the complete solution of the task is _k_ + 1.\n\nPolycarp has _M_ minutes of time. What is the maximum number of points he can earn?"},{"iden":"input","content":"The first line contains three integer numbers _n_, _k_ and _M_ (1 ≤ _n_ ≤ 45, 1 ≤ _k_ ≤ 45, 0 ≤ _M_ ≤ 2·109).\n\nThe second line contains _k_ integer numbers, values _t__j_ (1 ≤ _t__j_ ≤ 1000000), where _t__j_ is the time in minutes required to solve _j_\\-th subtask of any task."},{"iden":"output","content":"Print the maximum amount of points Polycarp can earn in _M_ minutes."},{"iden":"examples","content":"Input\n\n3 4 11\n1 2 3 4\n\nOutput\n\n6\n\nInput\n\n5 5 10\n1 2 4 8 16\n\nOutput\n\n7"},{"iden":"note","content":"In the first example Polycarp can complete the first task and spend 1 + 2 + 3 + 4 = 10 minutes. He also has the time to solve one subtask of the second task in one minute.\n\nIn the second example Polycarp can solve the first subtask of all five tasks and spend 5·1 = 5 minutes. Also he can solve the second subtasks of two tasks and spend 2·2 = 4 minutes. Thus, he earns 5 + 2 = 7 points in total."}],"translated_statement":[{"iden":"statement","content":"Polycarp 参加一场数学竞赛。他被给予 #cf_span[n] 道题目，每道题包含 #cf_span[k] 个子任务，编号为 #cf_span[1] 到 #cf_span[k]。解决第 #cf_span[j] 个子任务需要 #cf_span[tj] 分钟。因此，解决一个子任务所需的时间仅取决于其编号，而与具体题目无关。Polycarp 可以按任意顺序解决子任务。\n\n每解决一个子任务，他获得 1 分。因此，一道题的得分等于其被解决的子任务数量。此外，如果 Polycarp _完全_ 解决了一道题（即解决了它的全部 #cf_span[k] 个子任务），他将额外获得 1 分。因此，完全解决一道题的总得分为 #cf_span[k + 1]。\n\nPolycarp 总共有 #cf_span[M] 分钟的时间。他最多能获得多少分？\n\n第一行包含三个整数 #cf_span[n]、#cf_span[k] 和 #cf_span[M]（#cf_span[1 ≤ n ≤ 45]，#cf_span[1 ≤ k ≤ 45]，#cf_span[0 ≤ M ≤ 2·109]）。\n\n第二行包含 #cf_span[k] 个整数，即 #cf_span[tj]（#cf_span[1 ≤ tj ≤ 1000000]），其中 #cf_span[tj] 表示解决任意题目的第 #cf_span[j] 个子任务所需的时间（分钟）。\n\n请输出 Polycarp 在 #cf_span[M] 分钟内能获得的最大分数。\n\n在第一个示例中，Polycarp 可以完成第一道题，花费 #cf_span[1 + 2 + 3 + 4 = 10] 分钟。他还有 1 分钟时间解决第二道题的一个子任务。\n\n在第二个示例中，Polycarp 可以解决所有五个题目的第一个子任务，花费 #cf_span[5·1 = 5] 分钟；此外，他还可以解决其中两个题目的第二个子任务，花费 #cf_span[2·2 = 4] 分钟。因此，他总共获得 #cf_span[5 + 2 = 7] 分。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n]、#cf_span[k] 和 #cf_span[M]（#cf_span[1 ≤ n ≤ 45]，#cf_span[1 ≤ k ≤ 45]，#cf_span[0 ≤ M ≤ 2·109]）。第二行包含 #cf_span[k] 个整数，即 #cf_span[tj]（#cf_span[1 ≤ tj ≤ 1000000]），其中 #cf_span[tj] 表示解决任意题目的第 #cf_span[j] 个子任务所需的时间（分钟）。"},{"iden":"output","content":"请输出 Polycarp 在 #cf_span[M] 分钟内能获得的最大分数。"},{"iden":"examples","content":"输入\n3 4 11\n1 2 3 4\n输出\n6\n\n输入\n5 5 10\n1 2 4 8 16\n输出\n7"},{"iden":"note","content":"在第一个示例中，Polycarp 可以完成第一道题，花费 #cf_span[1 + 2 + 3 + 4 = 10] 分钟。他还有 1 分钟时间解决第二道题的一个子任务。\n\n在第二个示例中，Polycarp 可以解决所有五个题目的第一个子任务，花费 #cf_span[5·1 = 5] 分钟；此外，他还可以解决其中两个题目的第二个子任务，花费 #cf_span[2·2 = 4] 分钟。因此，他总共获得 #cf_span[5 + 2 = 7] 分。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the number of tasks, $ k $ the number of subtasks per task, and $ M $ the total available time.\n\nLet $ t_1, t_2, \\dots, t_k $ be the time required to solve subtask $ j $ (same for all tasks).\n\nDefine:\n- A **partial solution** of a task: solving a subset of its $ k $ subtasks, earning 1 point per solved subtask.\n- A **complete solution** of a task: solving all $ k $ subtasks, earning $ k + 1 $ points (i.e., $ k $ for subtasks + 1 bonus).\n\nLet $ x_i \\in \\{0, 1\\} $ indicate whether task $ i $ is completely solved ($ x_i = 1 $) or not ($ x_i = 0 $).\n\nLet $ s_{ij} \\in \\{0, 1\\} $ indicate whether subtask $ j $ of task $ i $ is solved individually (only if the task is not completely solved).\n\n**Constraints:**\n- Total time used:  \n  $$\n  \\sum_{i=1}^n x_i \\cdot \\sum_{j=1}^k t_j + \\sum_{i=1}^n \\sum_{j=1}^k (1 - x_i) \\cdot s_{ij} \\cdot t_j \\leq M\n  $$\n- Each $ x_i \\in \\{0,1\\} $, and for each $ i $, if $ x_i = 0 $, then $ s_{ij} \\in \\{0,1\\} $; if $ x_i = 1 $, then $ s_{ij} = 0 $ for all $ j $.\n\n**Objective:**\nMaximize total points:\n$$\n\\sum_{i=1}^n \\left( x_i \\cdot (k + 1) + \\sum_{j=1}^k (1 - x_i) \\cdot s_{ij} \\right)\n$$\n\n**Alternative formulation (simpler):**\n\nLet $ c $ be the number of completely solved tasks ($ 0 \\leq c \\leq n $).\n\nLet $ T = \\sum_{j=1}^k t_j $ be the time to complete one task.\n\nThen, time spent on complete tasks: $ c \\cdot T $\n\nRemaining time: $ M - c \\cdot T \\geq 0 $\n\nWith remaining time, solve individual subtasks from the remaining $ n - c $ tasks.\n\nSince subtasks are identical across tasks and order doesn't matter, we can treat all subtasks across incomplete tasks as a pool.\n\nLet $ r = M - c \\cdot T $. If $ r < 0 $, skip this $ c $.\n\nWe now want to maximize the number of subtasks solved from the $ n - c $ incomplete tasks, using time $ r $, where each subtask $ j $ costs $ t_j $, and we can solve at most $ n - c $ copies of each subtask $ j $ (one per incomplete task).\n\nSo, define a knapsack-like problem:\n\nLet $ a_j $ be the number of times subtask $ j $ is solved across incomplete tasks ($ 0 \\leq a_j \\leq n - c $).\n\nMaximize:\n$$\n\\sum_{j=1}^k a_j\n$$\nsubject to:\n$$\n\\sum_{j=1}^k a_j \\cdot t_j \\leq r, \\quad a_j \\in \\mathbb{Z}, \\quad 0 \\leq a_j \\leq n - c\n$$\n\nTotal points:\n$$\nc \\cdot (k + 1) + \\sum_{j=1}^k a_j\n$$\n\n**Final formal optimization problem:**\n\nMaximize over $ c \\in \\{0, 1, \\dots, n\\} $:\n$$\nc \\cdot (k + 1) + \\max_{\\substack{a_1, \\dots, a_k \\in \\mathbb{Z} \\\\ 0 \\leq a_j \\leq n - c \\\\ \\sum_{j=1}^k a_j t_j \\leq M - c T}} \\left( \\sum_{j=1}^k a_j \\right)\n$$\n\nWhere $ T = \\sum_{j=1}^k t_j $.\n\nIf $ M - c T < 0 $, then this $ c $ is infeasible.\n\nWe compute the inner max via dynamic programming over subtask types, bounded by $ n - c \\leq 45 $, and total time $ M \\leq 2 \\cdot 10^9 $, but since $ k \\leq 45 $ and $ n - c \\leq 45 $, we can use DP with state $ (j, \\text{time}) $, but time is too large.\n\n**Optimization note:** Since $ n - c \\leq 45 $, the total number of subtasks we can solve in incomplete tasks is at most $ 45 \\cdot 45 = 2025 $. So we can instead do DP over number of subtasks solved, with minimal time to achieve $ s $ subtasks.\n\nLet $ dp[s] = $ minimum time needed to solve exactly $ s $ subtasks across incomplete tasks (with at most $ n - c $ copies of each subtask type).\n\nWe can compute $ dp[s] $ for $ s = 0 $ to $ (n - c) \\cdot k $ using bounded knapsack (or unbounded knapsack with item limits).\n\nBut since $ k \\leq 45 $, $ n - c \\leq 45 $, then $ s_{\\max} \\leq 2025 $, and we can iterate over subtask types and use DP with array size 2026.\n\nThus, for each $ c \\in [0, n] $:\n\n1. Compute $ r = M - c \\cdot T $\n2. If $ r < 0 $, skip.\n3. Compute $ dp[0..S] $ where $ S = (n - c) \\cdot k $, with $ dp[s] = $ minimal time to solve $ s $ subtasks from the $ k $ types, with at most $ n - c $ of each type.\n4. Find $ s^* = \\max \\{ s \\mid dp[s] \\leq r \\} $\n5. Total points = $ c(k+1) + s^* $\n\nAnswer = $ \\max_{c=0}^n \\left( c(k+1) + s^* \\right) $\n\nThis is the formal mathematical formulation.","simple_statement":null,"has_page_source":false}