Không Thối Tiền

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John có $K$ đồng xu với các mệnh giá khác nhau. Anh ta cần thực hiện $N$ giao dịch mua hàng theo thứ tự. Mỗi giao dịch có một chi phí nhất định.

Với mỗi giao dịch, John phải dùng một đồng xu duy nhất để thanh toán. Đồng xu đó phải có giá trị lớn hơn hoặc bằng chi phí giao dịch. Tuy nhiên, người bán không thối tiền, nên phần dư sẽ bị mất. Mỗi đồng xu chỉ được dùng một lần, và khi dùng một đồng xu cho một giao dịch, nó sẽ thanh toán cho một dãy liên tiếp các giao dịch tiếp theo (bắt đầu từ giao dịch hiện tại) cho đến khi tổng chi phí vượt quá giá trị đồng xu.

Cụ thể hơn: John dùng các đồng xu theo thứ tự tùy ý. Mỗi đồng xu được dùng sẽ trả cho một đoạn liên tiếp các giao dịch tiếp theo chưa thanh toán, miễn tổng chi phí không vượt quá mệnh giá đồng xu. Các đoạn này phải phủ hết $N$ giao dịch.

Hãy tìm tổng mệnh giá lớn nhất của các đồng xu mà John không cần dùng (tức là giữ lại được nhiều tiền nhất), sao cho các đồng xu còn lại đủ để thanh toán tất cả $N$ giao dịch. Nếu không thể thanh toán hết, in $- 1$ .

Dữ liệu vào

Dòng đầu: hai số nguyên $K$ và $N$ .
$K$ dòng tiếp theo: mệnh giá của mỗi đồng xu.
$N$ dòng tiếp theo: chi phí của mỗi giao dịch.

Dữ liệu ra

Một số nguyên duy nhất: tổng mệnh giá lớn nhất giữ lại được, hoặc $- 1$ nếu không thể thanh toán hết.

Ràng buộc

$1 \leq K \leq 16$
$1 \leq N \leq 100 000$
Mệnh giá đồng xu: $1 \leq c_{i} \leq 10^{8}$
Chi phí giao dịch: $1 \leq p_{j} \leq 10 000$

Ví dụ

Input	Output	Giải thích
3 6 12 15 10 6 3 3 2 3 7	12	John dùng đồng xu 10 để trả 2 giao dịch đầu (6+3=9 ≤ 10), rồi dùng đồng xu 15 để trả 4 giao dịch còn lại (3+2+3+7=15 ≤ 15). Giữ lại đồng xu 12.
2 5 4 3 4 9 7 3 9	-1	Không có cách nào dùng 2 đồng xu (mệnh giá 4 và 3) để trả hết 5 giao dịch có tổng chi phí 32.

Bình luận

Không có bình luận tại thời điểm này.