Túi đồ với trọng lượng nhỏ

Bạn có một tập các món đồ, mỗi món có trọng lượng là số nguyên không vượt quá $8$. Một tập con các món đồ được gọi là tốt nếu tổng trọng lượng của các món trong tập con đó không vượt quá $W$.

Hãy tính tổng trọng lượng lớn nhất của một tập con tốt. Lưu ý rằng tập rỗng và toàn bộ tập ban đầu cũng được coi là tập con hợp lệ khi tính đáp án.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $W$ — tổng trọng lượng tối đa của một tập con tốt.
• Dòng thứ hai chứa $8$ số nguyên $cn{t}_1,cn{t}_2,\dots ,cn{t}_8$, trong đó $cn{t}_i$ là số món đồ có trọng lượng đúng bằng $i$.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng trọng lượng lớn nhất của một tập con tốt.

Ràng buộc

• $0\le W\le {10}^{18}$
• $0\le cn{t}_i\le {10}^{16}$ với mọi $1\le i\le 8$

Ví dụ