B. Math Show

Polycarp 参加一场数学竞赛。他被给予 #cf_span[n] 道题目，每道题包含 #cf_span[k] 个子任务，编号为 #cf_span[1] 到 #cf_span[k]。解决第 #cf_span[j] 个子任务需要 #cf_span[tj] 分钟。因此，解决一个子任务所需的时间仅取决于其编号，而与具体题目无关。Polycarp 可以按任意顺序解决子任务。 每解决一个子任务，他获得 1 分。因此，一道题的得分等于其被解决的子任务数量。此外，如果 Polycarp _完全_ 解决了一道题（即解决了它的全部 #cf_span[k] 个子任务），他将额外获得 1 分。因此，完全解决一道题的总得分为 #cf_span[k + 1]。 Polycarp 总共有 #cf_span[M] 分钟的时间。他最多能获得多少分？ 第一行包含三个整数 #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] 个子任务所需的时间（分钟）。 请输出 Polycarp 在 #cf_span[M] 分钟内能获得的最大分数。 在第一个示例中，Polycarp 可以完成第一道题，花费 #cf_span[1 + 2 + 3 + 4 = 10] 分钟。他还有 1 分钟时间解决第二道题的一个子任务。 在第二个示例中，Polycarp 可以解决所有五个题目的第一个子任务，花费 #cf_span[5·1 = 5] 分钟；此外，他还可以解决其中两个题目的第二个子任务，花费 #cf_span[2·2 = 4] 分钟。因此，他总共获得 #cf_span[5 + 2 = 7] 分。 ## Input 第一行包含三个整数 #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] 个子任务所需的时间（分钟）。 ## Output 请输出 Polycarp 在 #cf_span[M] 分钟内能获得的最大分数。 [samples] ## Note 在第一个示例中，Polycarp 可以完成第一道题，花费 #cf_span[1 + 2 + 3 + 4 = 10] 分钟。他还有 1 分钟时间解决第二道题的一个子任务。 在第二个示例中，Polycarp 可以解决所有五个题目的第一个子任务，花费 #cf_span[5·1 = 5] 分钟；此外，他还可以解决其中两个题目的第二个子任务，花费 #cf_span[2·2 = 4] 分钟。因此，他总共获得 #cf_span[5 + 2 = 7] 分。

Let $ n $ be the number of tasks, $ k $ the number of subtasks per task, and $ M $ the total available time. Let $ t_1, t_2, \dots, t_k $ be the time required to solve subtask $ j $ (same for all tasks). Define: - A **partial solution** of a task: solving a subset of its $ k $ subtasks, earning 1 point per solved subtask. - A **complete solution** of a task: solving all $ k $ subtasks, earning $ k + 1 $ points (i.e., $ k $ for subtasks + 1 bonus). Let $ x_i \in \{0, 1\} $ indicate whether task $ i $ is completely solved ($ x_i = 1 $) or not ($ x_i = 0 $). Let $ s_{ij} \in \{0, 1\} $ indicate whether subtask $ j $ of task $ i $ is solved individually (only if the task is not completely solved). **Constraints:** - Total time used: $$ \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 $$ - 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 $. **Objective:** Maximize total points: $$ \sum_{i=1}^n \left( x_i \cdot (k + 1) + \sum_{j=1}^k (1 - x_i) \cdot s_{ij} \right) $$ **Alternative formulation (simpler):** Let $ c $ be the number of completely solved tasks ($ 0 \leq c \leq n $). Let $ T = \sum_{j=1}^k t_j $ be the time to complete one task. Then, time spent on complete tasks: $ c \cdot T $ Remaining time: $ M - c \cdot T \geq 0 $ With remaining time, solve individual subtasks from the remaining $ n - c $ tasks. Since subtasks are identical across tasks and order doesn't matter, we can treat all subtasks across incomplete tasks as a pool. Let $ r = M - c \cdot T $. If $ r < 0 $, skip this $ c $. We 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). So, define a knapsack-like problem: Let $ a_j $ be the number of times subtask $ j $ is solved across incomplete tasks ($ 0 \leq a_j \leq n - c $). Maximize: $$ \sum_{j=1}^k a_j $$ subject to: $$ \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 $$ Total points: $$ c \cdot (k + 1) + \sum_{j=1}^k a_j $$ **Final formal optimization problem:** Maximize over $ c \in \{0, 1, \dots, n\} $: $$ c \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) $$ Where $ T = \sum_{j=1}^k t_j $. If $ M - c T < 0 $, then this $ c $ is infeasible. We 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. **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. Let $ dp[s] = $ minimum time needed to solve exactly $ s $ subtasks across incomplete tasks (with at most $ n - c $ copies of each subtask type). We can compute $ dp[s] $ for $ s = 0 $ to $ (n - c) \cdot k $ using bounded knapsack (or unbounded knapsack with item limits). But 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. Thus, for each $ c \in [0, n] $: 1. Compute $ r = M - c \cdot T $ 2. If $ r < 0 $, skip. 3. 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. 4. Find $ s^* = \max \{ s \mid dp[s] \leq r \} $ 5. Total points = $ c(k+1) + s^* $ Answer = $ \max_{c=0}^n \left( c(k+1) + s^* \right) $ This is the formal mathematical formulation.