Math Show

题意翻译

多鱼参加了一个数学节目。他被赋予N个任务，每个由K个子任务组成，编号为1到K。这需要他在t[j]分钟内解决第j个子任务。因此，解答子任务所需的时间只取决于它的索引，而不取决于任务本身。多鱼可以按任何顺序解子任务。 通过解决任意问题的次要任务，他得了一分。这样，任务的点数就等于其中解出的子任务的个数。此外，如果聚鱼完全解决了这个问题（解决了它所有的子任务的K），他会多得一分。这样，他所得到的任务完全解的总点数为K+1。 多鱼有m分钟的时间。他最多能挣多少分？ 第一行3个整数n,k,N。 第二行k个整数t[j]

题目描述

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. By 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 $ . Polycarp has $ M $ minutes of time. What is the maximum number of points he can earn?

输入输出格式

输入格式

The first line contains three integer numbers $ n $ , $ k $ and $ M $ ( $ 1<=n<=45 $ , $ 1<=k<=45 $ , $ 0<=M<=2·10^{9} $ ). The 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.

输出格式

Print the maximum amount of points Polycarp can earn in $ M $ minutes.

输入输出样例

输入样例 #1

3 4 11
1 2 3 4

输出样例 #1

6

输入样例 #2

5 5 10
1 2 4 8 16

输出样例 #2

7

说明

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. In 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.