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?


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
3 4 11
1 2 3 4

Output
6

Input
5 5 10
1 2 4 8 16

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

Difficulty: MEDIUM_HARD
Tags: Complete search

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
(n, k, m) = [int(i) for i in input().split()]
t = sorted([int(i) for i in input().split()])
st = sum(t)
best = -1
for s in range(min(n, m // st) + 1):
	score = s * (k + 1)
	rm = m - s * st
	for j in range(k):
		q = min(n - s, rm // t[j])
		rm -= q * t[j]
		score += q
	best = max(best, score)
print(best)


(n, k, m) = list(map(int, input().split()))
t = sorted(map(int, input().split()))
res = 0
for i in range(n + 1):
	rem = m - i * sum(t)
	if rem < 0:
		break
	r = i * (k + 1)
	for j in range(k):
		d = min(rem // t[j], n - i)
		rem -= d * t[j]
		r += d
	res = max(res, r)
print(res)


def solve(n, k, M, t):
	task_sum = sum(t)
	t = sorted(t)
	best = 0
	for tasks_completed in range(n + 1):
		minutes_spent_on_full_tasks = tasks_completed * task_sum
		if minutes_spent_on_full_tasks > M:
			break
		total_points = tasks_completed * k + tasks_completed
		remaining_time = M - minutes_spent_on_full_tasks
		for subtask_time in t:
			subtasks_left = n - tasks_completed
			smaller_subtasks_time = subtasks_left * subtask_time
			if smaller_subtasks_time <= remaining_time:
				remaining_time -= smaller_subtasks_time
				total_points += subtasks_left
			else:
				total_points += remaining_time // subtask_time
				break
		best = max(total_points, best)
	return best

def main():
	(n, k, M) = [int(x) for x in input().split(' ')]
	t = [int(x) for x in input().split(' ')]
	res = solve(n, k, M, t)
	print(res)
main()


(n, k, M) = [int(i) for i in input().split(' ')]
tasks = [int(i) for i in input().split(' ')]
tasks = sorted(tasks)
ans = 0
for i in range(n + 1):
	remaining_time = M - i * sum(tasks)
	if remaining_time < 0:
		break
	value = (k + 1) * i
	for j in range(k):
		for take in range(n - i):
			if remaining_time >= tasks[j]:
				value += 1
				remaining_time -= tasks[j]
	ans = max(ans, value)
print(ans)


def find_max(n, k, m, ts):
	out = 0
	ts.sort()
	for i in range(n + 1):
		cur = 0
		time = sum(ts) * i
		if time > m:
			break
		else:
			cur += (k + 1) * i
		time_left = m - time
		cur_subtask = 0
		while time_left > 0 and cur_subtask < k:
			solved = min(n - i, time_left // ts[cur_subtask])
			if solved == 0:
				break
			time_left -= solved * ts[cur_subtask]
			cur += solved
			cur_subtask += 1
		out = max(out, cur)
	return out

def main():
	(n, k, m) = (int(x) for x in input().split())
	ts = [int(x) for x in input().split()]
	print(find_max(n, k, m, ts))
main()


(n, k, M) = map(int, input().split())
t = sorted(list(map(int, input().split())))
pt = t[:]
for i in range(1, k):
	pt[i] += pt[i - 1]
(ans, r) = (0, k - 1)
for i in range(0, n + 1):
	if pt[-1] * i > M:
		break
	m = M - pt[-1] * i
	while r != -1 and pt[r] * (n - i) > m:
		r -= 1
	m -= 0 if r == -1 else pt[r] * (n - i)
	ans = max(ans, i * (k + 1) + (r + 1) * (n - i) + (m // t[r + 1] if r < k - 1 else 0))
print(ans)


from itertools import accumulate
from bisect import *
(n, k, m) = list(map(int, input().split()))
t = sorted(map(int, input().split()))
res = 0
for x in range(min(n, m // sum(t)) + 1):
	mm = m - x * sum(t)
	r = x * (k + 1)
	for (i, ti) in enumerate(t):
		for _ in range(n - x):
			if mm >= ti:
				mm -= ti
				r += 1 if i < k - 1 else 2
	res = max(res, r)
print(res)


ins = lambda : map(int, input().split())
(n, k, m) = ins()
c = list(ins())
c.sort()
s = sum(c)
ans = 0
for i in range(min(n, m // s) + 1):
	(t, a) = (m - s * i, i * k + i)
	for j in range(k):
		for l in range(n - i):
			if t - c[j] < 0:
				break
			t -= c[j]
			a += 1
		if t - c[j] < 0:
			break
	ans = max(ans, a)
print(ans)


(n, k, M) = map(int, input().split())
t = list(map(int, input().split()))
answer = []
for good in range(n + 1):
	local_answer = (k + 1) * good
	m = M - sum(t) * good
	if m < 0:
		continue
	todo = sorted(t * (n - good), key=lambda x: -x)
	while todo and m:
		if m < todo[-1]:
			break
		m -= todo.pop()
		local_answer += 1
	answer.append(local_answer)
print(max(answer))


def solve(n, k, M, t):
	t.sort()
	k = len(t)
	T = sum(t)
	max_score = 0
	for fully_solved in range(min(n, M // T) + 1):
		score_1 = fully_solved * (k + 1)
		score_2 = 0
		remaining_time = M - T * fully_solved
		remaining_problems = n - fully_solved
		if remaining_problems > 0:
			level = 0
			while level < k:
				level_coeff = 1 if level + 1 < k else 2
				time_to_solve_level = t[level] * remaining_problems
				if time_to_solve_level <= remaining_time:
					score_2 += remaining_problems * level_coeff
					remaining_time -= time_to_solve_level
				else:
					score_2 += remaining_time // t[level] * level_coeff
					break
				level += 1
		score = score_1 + score_2
		max_score = max(score, max_score)
	return max_score

def main():
	(n, k, M) = map(int, input().split())
	t = list(map(int, input().split()))
	print(solve(n, k, M, t))
main()


f = lambda : map(int, input().split())
(n, k, m) = f()
p = sorted(f())
x = 0
s = sum(p)
for j in range(n + 1):
	t = m - j * s
	if t < 0:
		break
	y = k * j + j
	for i in p:
		d = min(n - j, t // i)
		y += d
		t -= d * i
	x = max(x, y)
print(x)


(n, k, M) = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
b.sort()
suma = sum(b)
ans = 0
for total in range(n + 1):
	m = M - total * suma
	if m < 0:
		break
	r = (k + 1) * total
	for x in b:
		sol = min(n - total, m // x)
		r += sol
		m -= sol * x
	ans = max(ans, r)
print(ans)


(n, k, m) = map(int, input().split())
nums = list(map(int, input().split()))
result = -1
alltime = sum(nums)
for made in range(n + 1):
	if alltime * made > m:
		break
	currentres = (k + 1) * made
	currenttime = m - made * alltime
	available = []
	for item in nums:
		available.extend([item] * (n - made))
	available = sorted(available)
	for item in available:
		if currenttime < item:
			break
		currenttime -= item
		currentres += 1
	result = max(result, currentres)
print(result)


(n, k, M) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
S = sum((t[j] for j in range(k)))
ans = 0
for i in range(n + 1):
	if i * S > M:
		break
	else:
		p = (k + 1) * i
		R = M - i * S
		for j in range(k):
			if R < t[j]:
				break
			else:
				q = min(n - i, R // t[j])
				R -= q * t[j]
				p += q
		ans = max(ans, p)
print(ans)


(n, k, m) = list(map(int, input().split()))
t = sorted(map(int, input().split()))
res = 0
for x in range(min(m // sum(t), n) + 1):
	rem = m - x * sum(t)
	r = x * (k + 1)
	for i in range(k):
		div = min(rem // t[i], n - x)
		rem -= div * t[i]
		r += div
	res = max(res, r)
print(res)


(n, k, m) = list(map(int, input().split()))
l = list(map(int, input().split()))
l.sort()
s = sum(l)
ans = 0
for i in range(n + 1):
	mi = m - s * i
	if mi < 0:
		break
	cnt = (k + 1) * i
	for j in range(k):
		x = min(mi // l[j], n - i)
		cnt += x
		mi -= l[j] * x
	ans = max(ans, cnt)
print(ans)


(n, k, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
sum_row = 0
for elem in a:
	sum_row += elem
max_ans = 0
for i in range(min(n + 1, m // sum_row + 1)):
	ans = i * (k + 1)
	m1 = m - sum_row * i
	for j in range(k):
		t = (n - i) * a[j]
		if t <= m1:
			m1 -= t
			ans += n - i
		else:
			ans += m1 // a[j]
			break
	max_ans = max(max_ans, ans)
print(max_ans)


(n, k, M) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
suma = sum(a)
ans = 0
for total in range(n + 1):
	m = M - suma * total
	if m < 0:
		break
	r = total * (k + 1)
	for x in a:
		solved = min(n - total, m // x)
		r += solved
		m -= solved * x
	ans = max(ans, r)
print(ans)


(n, k, m) = map(int, input().split())
lst = list(map(int, input().split()))
l = []
s = sum(lst)
lst.sort()
g = n
h = m
for r in range(g + 1):
	ans = 0
	m = h
	n = g - r
	if s * r <= m:
		ans += (k + 1) * r
		m = m - s * r
		c = 0
		while 1:
			if c >= k:
				break
			t = m // lst[c]
			if t <= 0:
				break
			if t > n:
				m = m - n * lst[c]
				ans += n
			else:
				m = m - t * lst[c]
				ans += t
			c += 1
		l.append(ans)
	else:
		break
print(max(l))


(n, k, M) = map(int, input().split())
time_list = sorted(list(map(int, input().split())))
sum1 = sum(time_list)
tries_list = []
for i in range(n + 1):
	m = M
	c = 0
	for j in range(i):
		if m - sum1 >= 0:
			m -= sum1
			c += k + 1
		else:
			break
	for j in range(k):
		for _ in range(n - i):
			if m - time_list[j] >= 0:
				m -= time_list[j]
				c += 1
			else:
				break
	tries_list.append(c)
print(max(tries_list))


(n, k, m) = list(map(int, input().split()))
t = sorted(map(int, input().split()))
res = 0
for x in range(min(n, m // sum(t)) + 1):
	mm = m - x * sum(t)
	r = x * (k + 1)
	for (i, ti) in enumerate(t):
		div = min(mm // ti, n - x)
		mm -= div * ti
		r += div if i < k - 1 else div * 2
	res = max(res, r)
print(res)


from functools import reduce
(n, k, m) = list(map(int, input().split()))
t = list(map(int, input().split()))
t.sort()
sum = reduce(lambda x, y: x + y, t)
mx = 0
full = 0
while full <= n and full * sum <= m:
	cnt = full * k + full
	free_time = m - sum * full
	for time in t:
		tasks = min(n - full, free_time // time)
		cnt += tasks
		free_time -= tasks * time
	mx = max(mx, cnt)
	full += 1
print(mx)


(n, k, M) = map(int, input().split())
t = sorted(map(int, input().split()))

def calc(x):
	tot = x * sum(t)
	if tot > M:
		return 0
	tans = x * (k + 1)
	for i in range(k - 1):
		if t[i] * (n - x) + tot <= M:
			tot += t[i] * (n - x)
			tans += n - x
		else:
			tans += (M - tot) // t[i]
			break
	return tans
print(max([calc(x) for x in range(n + 1)]))


[n, k, M] = list(map(int, input().split()))
t = list(map(int, input().split()))
t.sort()
tot = sum(t)
res = 0
for x in range(n + 1):
	need = x * tot
	if need <= M:
		cnt = x * (k + 1)
		r = M - need
		j = 0
		while r > 0 and j < k:
			if t[j] * (n - x) <= r:
				cnt += n - x
				r -= t[j] * (n - x)
				j += 1
			else:
				cnt += r // t[j]
				r -= r // t[j] * t[j]
				break
		res = max(res, cnt)
print(res)


from heapq import *
(N, K, M) = map(int, input().split())
T = list(map(int, input().split()))

def rest(m, n):
	pq = []
	for i in range(n):
		for j in range(K):
			heappush(pq, T[j])
	cnt = 0
	while len(pq) > 0 and m >= pq[0]:
		subtask = heappop(pq)
		m -= subtask
		cnt += 1
	return cnt
ans = -1
for i in range(N + 1):
	time_ = M - sum(T) * i
	if time_ < 0:
		continue
	score = 1 * i + K * i + rest(time_, N - i)
	ans = max(ans, score)
print(ans)


(n, k, M) = map(int, input().split())
t = list(map(int, input().split()))
sumt = sum(t)
score = 0
t.sort()
for i in range(n + 1):
	m = M - sumt * i
	if m < 0:
		break
	r = i * (k + 1)
	for x in t:
		resheno = min(n - i, m // x)
		r += resheno
		m -= resheno * x
	score = max(score, r)
print(score)


def list_input():
	return list(map(int, input().split()))

def map_input():
	return map(int, input().split())

def map_string():
	return input().split()
(n, k, m) = map_input()
a = list_input()
a.sort()
sm = sum(a)
ans = 0
for i in range(n + 1):
	if sm * i > m:
		break
	m1 = m - sm * i
	cnt = [n - i] * k
	cur = 0
	res = (k + 1) * i
	while m1 > 0:
		if cur >= k or a[cur] > m1:
			break
		x = min(m1 // a[cur], cnt[cur])
		res += x
		m1 -= x * a[cur]
		cur += 1
	ans = max(res, ans)
print(ans)


(n, k, m) = map(int, input().split())
t = sorted(map(int, input().split()), key=int)
s = sum(t)
ans = 0
for i in range(n + 1):
	curr_ans = i * (k + 1)
	tot = m - i * s
	if tot < 0:
		break
	for x in t:
		c = min(n - i, tot // x)
		if not c:
			break
		tot -= c * x
		curr_ans += c
	ans = max(ans, curr_ans)
print(ans)


(n, k, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
sm = sum(l)
ans = 0
for i in range(n + 1):
	if sm * i > m:
		break
	m1 = m - sm * i
	cnt = [n - i] * k
	cur = 0
	res = (k + 1) * i
	while m1 > 0:
		if cur >= k or l[cur] > m1:
			break
		x = min(m1 // l[cur], cnt[cur])
		res += x
		m1 -= x * l[cur]
		cur += 1
	ans = max(res, ans)
print(ans)


(n, k, m) = list(map(int, input().split()))
tt = list(map(int, input().split()))
tt.sort()
s = sum(tt)
ans = 0

def check(x, m):
	ret = (k + 1) * x
	m -= s * x
	if m < 0:
		return -1
	for i in range(k):
		if tt[i] * (n - x) <= m:
			m -= tt[i] * (n - x)
			ret += n - x
		else:
			ret += m // tt[i]
			m -= m // tt[i] * tt[i]
		if m <= 0:
			break
	return ret
for i in range(n + 1):
	ans = max(ans, check(i, m))
print(ans)


(n, k, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
ans = 0
for i in range(n + 1):
	t = s * i
	cur = (k + 1) * i
	if t > m:
		break
	t = m - t
	for j in range(k):
		x = min(t // a[j], n - i)
		t -= x * a[j]
		cur += x
	ans = max(ans, cur)
print(ans)


(n, k, m) = [int(x) for x in input().split()]
a = sorted([int(x) for x in input().split()])
et = sum(a)
es = k + 1
ans = []
for i in range(n + 1):
	ts = es * i
	ht = m - et * i
	if ht < 0:
		break
	for p in a:
		s = min(ht // p, n - i)
		ht -= s * p
		ts += s
	ans.append(ts)
ans.sort()
print(ans[-1])


(n, k, M) = map(int, input().split())
T = sorted(map(int, input().split()))
sT = sum(T)

def it(p):
	score = p * (k + 1)
	m = M - p * sT
	if m < 0:
		return 0
	q = n - p
	for t in T:
		if m > q * t:
			m -= q * t
			score += q
		else:
			score += m // t
			break
	return score
print(max((it(i) for i in range(n + 1))))


def zhadnik(n, k, M, t):
	ans = 0
	i = 0
	while i < k and M >= t[i]:
		temp = M // t[i]
		if temp <= n:
			ans += temp
			M -= temp * t[i]
		else:
			ans += n
			M -= n * t[i]
		i += 1
	return ans
(n, k, M) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
all_task_time = sum(t)
ans = zhadnik(n, k, M, t)
l = 1
while l <= n and M - all_task_time * l >= 0:
	res = l * (k + 1) + zhadnik(n - l, k, M - all_task_time * l, t)
	if res > ans:
		ans = res
	l += 1
print(ans)


(n, k, m) = map(int, input().split())
line = list(map(int, input().split()))
line.sort()
t = sum(line)
ans = 0
for i in range(n + 1):
	if m - t * i < 0:
		break
	mm = m - t * i
	ans1 = (k + 1) * i
	for j in range(k):
		ans1 += min(n - i, mm // line[j])
		mm -= min(n - i, mm // line[j]) * line[j]
	ans = max(ans, ans1)
print(ans)


import sys
(n, k, m) = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
if n * total <= m:
	print(n * (k + 1))
	exit()
ans = 0
for complete in range(n):
	if complete * total > m:
		break
	items = a * (n - complete)
	dp = [-1] * (len(items) + 1)
	dp[0] = m - complete * total
	for x in items:
		for i in range(len(items) - 1, -1, -1):
			dp[i + 1] = max(dp[i + 1], dp[i] - x)
	for i in range(len(items), -1, -1):
		if dp[i] >= 0:
			ans = max(ans, i + complete * (k + 1))
			break
print(ans)


(n, k, m) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
s = []
for i in range(min(m // sum(t) + 1, n)):
	y = m
	x = i * (k + 1)
	y -= i * sum(t)
	f = n - i
	for j in range(k - 1):
		x += min(f, y // t[j])
		y -= min(f, y // t[j]) * t[j]
	x += 2 * min(f, y // t[k - 1])
	y -= min(f, y // t[k - 1]) * t[k - 1]
	s.append(x)
print(max(s))


import sys
input = sys.stdin.readline
from collections import defaultdict
(n, k, m) = map(int, input().split())
l = list(map(int, input().split()))
s = sum(l)
ans = 0
for x in range(n + 1):
	left = m - s * x
	if left < 0:
		continue
	else:
		temp = (k + 1) * x
		t = sorted(l * (n - x))
		z = len(t)
		i = 0
		while i < z:
			cur = t[i]
			if left >= cur:
				left -= cur
				temp += 1
				i += 1
			else:
				break
		ans = max(ans, temp)
print(ans)


from itertools import accumulate
from bisect import *
(n, k, m) = list(map(int, input().split()))
t = sorted(map(int, input().split()))
res = 0
s = sum(t)
ps = list(accumulate(t))
for x in range(min(n, m // s) + 1):
	rem = m - x * s
	if x < n:
		y = bisect_right(ps, rem / (n - x))
		rem -= (n - x) * (ps[y - 1] if y > 0 else 0)
		if y < k:
			z = rem // t[y]
		else:
			z = 0
	else:
		y = z = 0
	r = x * (k + 1) + y * (n - x) + z + (n - x if y == k else 0) + (z if y == k - 1 else 0)
	res = max(res, r)
print(res)


(n, k, m) = list(map(int, input().split()))
t = list(map(int, input().split()))
t.sort()
s = sum(t)
mmm = 0
for i in range(n + 1):
	if i * s > m:
		break
	tm = m - i * s
	c = k * i + i
	for j in range(k):
		c += min(tm // t[j], n - i)
		tm -= min(tm // t[j], n - i) * t[j]
	mmm = max(mmm, c)
print(mmm)


(n, k, M) = map(int, input().split())
t = [int(c) for c in input().split()]
t.sort()
res = 0
s = sum(t)
for to in range(n + 1):
	m = M - to * s
	if m < 0:
		break
	r = (k + 1) * to
	for i in t:
		r += min(n - to, m // i)
		m -= min(n - to, m // i) * i
	res = max(res, r)
print(res)


(n, k, m) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p.sort()
ans = 0
for i in range(n + 1):
	l = m
	for j in range(k):
		l -= p[j] * i
	if l < 0:
		break
	cr = i * k + i
	for j in range(k):
		if l < p[j]:
			break
		c = min(l // p[j], n - i)
		l -= p[j] * c
		cr += c
	ans = max(ans, cr)
print(ans)


(n, k, M) = map(int, input().split(' '))
t = map(int, input().split(' '))
st_but_long = list(sorted(t))
max_point = 0
for finished_tasks in range(n + 1):
	iteration_point = 0
	remaining_minutes = M
	remaining_minutes -= sum(st_but_long) * finished_tasks
	iteration_point += (k + 1) * finished_tasks if finished_tasks > 0 and remaining_minutes >= 0 else 0
	for subtask in range(k - 1):
		if remaining_minutes > 0:
			total_accomodated_columns = min(n - finished_tasks, remaining_minutes // st_but_long[subtask])
			remaining_minutes -= total_accomodated_columns * st_but_long[subtask]
			iteration_point += total_accomodated_columns if remaining_minutes >= 0 else 0
	max_point = max(max_point, iteration_point)
print(max_point)


def main():
	(n, k, m) = map(int, input().split(' '))
	time = list(map(int, input().split(' ')))
	time = sorted(time)
	ans = 0
	for i in range(n + 1):
		remain_time = m - i * sum(time)
		if remain_time < 0:
			break
		value = (k + 1) * i
		for j in range(k):
			for take in range(n - i):
				if remain_time >= time[j]:
					value = value + 1
					remain_time = remain_time - time[j]
		ans = max(ans, value)
	print(ans)
main()


(n, k, M) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
a.sort()
rimasto = []
punteggio = []
s = sum(a)
for i in range(n + 1):
	if i * s <= M:
		rimasto.append(M - i * s)
		punteggio.append(i * (k + 1))
for i in range(len(rimasto)):
	t = rimasto[i]
	task = 0
	while t > 0 and task < k:
		j = t // a[task]
		j = min(j, n - i)
		t = t - j * a[task]
		punteggio[i] += j
		task += 1
print(max(punteggio))


(n, k, M) = map(int, input().split())
score = sorted([int(x) for x in input().split()])
s = sum(score)
ans = 0
for i in range(n + 1):
	m = M - s * i
	if m < 0:
		break
	r = (k + 1) * i
	for x in score:
		solved = min(n - i, m // x)
		r += solved
		m -= solved * x
	ans = max(ans, r)
print(ans)


(n, k, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
maximum = 0
i = 0
while i <= n and i * s <= m:
	cur = m - s * i
	ans = (k + 1) * i
	for pos in range(k):
		if cur < a[pos]:
			break
		c = min(n - i, cur // a[pos])
		cur -= a[pos] * c
		ans += c
	maximum = max(maximum, ans)
	i += 1
print(maximum)


(n, k, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
ans = 0
sm = sum(a)
ans = 0
for i in range(min(n, m // sm) + 1):
	ansn = (k + 1) * i
	tm = m - i * sm
	for j in range(k):
		q = min(n - i, max(0, tm // a[j]))
		ansn += q
		tm -= q * a[j]
	ans = max(ansn, ans)
print(ans)


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
(n, k, m) = map(int, input().split())
a = sorted(map(int, input().split()))
s = sum(a)
ans = 0
for i in range(n + 1):
	t = m - s * i
	p = (k + 1) * i
	if t < 0:
		break
	rest = n - i
	for ai in a:
		q = min(rest, t // ai)
		t -= q * ai
		p += q
	ans = max(ans, p)
print(ans)