#P846B. Math Show
-
ID: 3981
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Math Show
No submission language available for this problem.
Description
Polycarp takes part in a math show. He is given n tasks, each consists of k subtasks, numbered 1 through k. It takes him tj 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·109).
The second line contains k integer numbers, values tj (1 ≤ tj ≤ 1000000), where tj 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.
Input
The first line contains three integer numbers n, k and M (1 ≤ n ≤ 45, 1 ≤ k ≤ 45, 0 ≤ M ≤ 2·109).
The second line contains k integer numbers, values tj (1 ≤ tj ≤ 1000000), where tj is the time in minutes required to solve j-th subtask of any task.
Output
Print the maximum amount of points Polycarp can earn in M minutes.
Samples
3 4 11
1 2 3 4
6
5 5 10
1 2 4 8 16
7
Note
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.