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: interview

Starter code:

Solutions:
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 = [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 = list(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 = map(int,input().split())

T = sorted(map(int,input().split()))

sT = sum(T)

def it(p):
  # 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)))

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)


def solve(n, k, M, t):
    '''
    >>> solve(3, 4, 11, [1, 2, 3, 4])
    6
    >>> solve(5, 5, 10, [1, 2, 4, 8, 16])
    7
    >>> solve(3, 2, 4, [1, 1])
    6
    >>> solve(5, 2, 10, [2, 3])
    6
    '''
    t.sort()
    k = len(t)

    T = sum(t)

    max_score = 0

    for fully_solved in range(min(n, M // T) + 1):
        # Try to fully solve fully_solved problems, remainder is for remaining subproblems
        score_1 = fully_solved * (k + 1) # For fully solved

        score_2 = 0 # For partially solved
        remaining_time = M - T * fully_solved
        remaining_problems = n - fully_solved

        if remaining_problems > 0:
            level = 0
            while level < k:
                # remaining_time > 0 and level < k:
                level_coeff = 1 if level + 1 < k else 2 # last_level
                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 = list(map(int, input().split()))
    t = list(map(int, input().split()))
    print(solve(n, k, M, t))


def __starting_point():
    main()


__starting_point()



def find_max(n, k, m, ts):
    out = 0

    ts.sort()

    for i in range(n+1): # first i tasks solved completely
        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))


def __starting_point():
    main()



__starting_point()

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()))

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 = 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)

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()) # n, k <= 45
t = list(map(int, input().split()))
t.sort()

all_task_time = sum(t) # время на решение целой задачи (всех подзадач)

# если бы не было премии за решение всей задачи - тогда только жадник
ans = zhadnik(n, k, M, t)

# попробуем улучшить результат за счет премии за решение l полных задач:
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 = [int(i) for i in input().split()]
t = sorted([int(i) for i in input().split()])
st = sum(t)

best = -1

# try all values for solved tasks
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)

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)

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)

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)

def list_input():
    return list(map(int,input().split()))
def map_input():
    return list(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)  
    



# import sys
# sys.stdin = open('in', 'r')

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)


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 = list(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 = 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 = list(map(int, input().split()))
t = sorted(map(int, input().split()))
st = sum(t)
res = 0
for x in range(min(m//st, n)+1):
    rem = m-x*st
    r = x*(k+1)
    # for i in range(k):
        # y = min(rem//t[i], n-x)
        # rem -= t[i]*y
        # m += y
    for i in range(k):
        for _ in range(n-x):
            if rem >= t[i]:
                rem -= t[i]
                r += 1
    res = max(res, r)
print(res)

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

ins = lambda : list(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 = 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()))
t = sorted(map(int, input().split()))
st = sum(t)
res = 0
for x in range(min(m//st,n)+1):
    rem = m - x*st
    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)