You have a set of items, each having some integer weight not greater than $8$. You denote that a subset of items is good if total weight of items in the subset does not exceed $W$.

You want to calculate the maximum possible weight of a good subset of items. Note that you have to consider the empty set and the original set when calculating the answer.


-----Input-----

The first line contains one integer $W$ ($0 \le W \le 10^{18}$) — the maximum total weight of a good subset.

The second line denotes the set of items you have. It contains $8$ integers $cnt_1$, $cnt_2$, ..., $cnt_8$ ($0 \le cnt_i \le 10^{16}$), where $cnt_i$ is the number of items having weight $i$ in the set.


-----Output-----

Print one integer — the maximum possible weight of a good subset of items.


-----Examples-----
Input
10
1 2 3 4 5 6 7 8

Output
10

Input
0
0 0 0 0 0 0 0 0

Output
0

Input
3
0 4 1 0 0 9 8 3

Output
3

Difficulty: HARD
Tags: Dynamic programming

Graph traversal

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
from math import gcd
from itertools import product
w = int(input())
c = list(map(int, input().split()))
sm = sum([c[i] * (i + 1) for i in range(8)])
per = 1
if sm < w:
	print(sm)
	exit()
elif sm < w + 64:
	ans = 0
	ls = [list(range(0, min(c[i] + 1, 8))) for i in range(8)]
	for x in product(*ls):
		tmp = 0
		for i in range(8):
			tmp += (i + 1) * x[i]
		if sm - tmp <= w:
			ans = max(ans, sm - tmp)
	print(ans)
	exit()
else:
	for i in range(8):
		for j in range(min(c[i], 2520 // (i + 1))):
			per |= per << i + 1
			per &= (1 << 2521) - 1
rem = w % 2520
ans = w
while per & 1 << rem == 0:
	ans -= 1
	rem -= 1
print(ans)


import os
import sys
from functools import lru_cache, reduce
from io import BytesIO
sys.setrecursionlimit(30000)
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
print = lambda x: os.write(1, str(x).encode())

def main():
	init_w = int(input())
	cnt = [int(i) for i in input().split()]
	dp_cnt = [min(cnt_i, 16) for (i, cnt_i) in enumerate(cnt)]
	greedy_cnt = [cnt_i - dp_cnt_i for (cnt_i, dp_cnt_i) in zip(cnt, dp_cnt)]
	(i, w) = (8, init_w)
	while i > 0 and w > 0:
		w -= i * greedy_cnt[i - 1]
		if w < 0:
			w %= i
			for j in range(2):
				w += i if min(greedy_cnt[i - 1], dp_cnt[i - 1]) > j + 1 else 0
		i -= 1
	weights = reduce(list.__add__, (dp_cnt_i * [i + 1] for (i, dp_cnt_i) in enumerate(dp_cnt)))

	@lru_cache(maxsize=None)
	def solve(i, val):
		if val == 0:
			return True
		if i == 0:
			return False
		return solve(i - 1, val) or solve(i - 1, val - weights[i - 1])
	for val in range(min(w, sum(weights)), -1, -1):
		if solve(len(weights), val):
			print(init_w - w + val)
			break
main()


import time
import random
W = int(input())
M = [int(a) for a in input().split()]
A = [0] * 8
sTime = time.time()
s = 0
mi = 10 ** 20
for i in range(8):
	if s + M[i] * (i + 1) <= W:
		s += M[i] * (i + 1)
		A[i] = M[i]
	else:
		t = (W - s) // (i + 1)
		s += t * (i + 1)
		A[i] += t
	if s <= W:
		mi = min(mi, W - s)
while time.time() - sTime < 1.7:
	i = random.randrange(8)
	a = random.randrange(2)
	if W - s >= 20 or (s - W < 10 and a == 0):
		if A[i] < M[i]:
			A[i] += 1
			s += i + 1
	elif A[i] > 0:
		A[i] -= 1
		s -= i + 1
	if s <= W:
		mi = min(mi, W - s)
print(W - mi)