Farmer John đang ở chợ để mua vật tư cho trang trại. Trong túi ông có \(K\) đồng xu (\(1 \le K \le 16\)), mỗi đồng có giá trị trong khoảng \(1..100\,000\,000\). FJ muốn thực hiện một dãy gồm \(N\) giao dịch mua hàng (\(1 \le N \le 100\,000\)), trong đó giao dịch thứ \(i\) có giá \(c(i)\) đơn vị tiền (\(1 \le c(i) \le 10\,000\)). Trong quá trình thực hiện lần lượt các giao dịch này, thỉnh thoảng ông có thể dừng lại và dùng một đồng xu duy nhất để thanh toán cho tất cả các món hàng đã mua kể từ lần thanh toán trước đó (dĩ nhiên, đồng xu được dùng phải có giá trị đủ lớn để thanh toán toàn bộ số tiền này). Thật không may, những người bán hàng ở chợ hoàn toàn không có tiền thối, vì vậy mỗi khi FJ dùng một đồng xu có giá trị lớn hơn số tiền phải trả, ông đáng tiếc không nhận lại được tiền thừa!

Hãy tính số tiền lớn nhất FJ có thể còn lại sau khi thực hiện lần lượt cả \(N\) giao dịch mua hàng. In ra \(-1\) nếu FJ không thể thực hiện tất cả các giao dịch.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(K\) và \(N\).
• Các dòng \(2..1+K\): mỗi dòng chứa giá trị của một đồng xu của FJ.
• Các dòng \(2+K..1+N+K\): \(N\) dòng này chứa chi phí của các giao dịch FJ dự định thực hiện.

Dữ liệu ra

• Dòng 1 chứa số tiền lớn nhất FJ có thể còn lại, hoặc \(-1\) nếu FJ không thể hoàn thành tất cả các giao dịch mua hàng.

Ví dụ

3 6
12
15
10
6
3
3
2
3
7

12

Nguồn

USACO 2013 November Contest, Gold — Problem 3: No Change

Tác giả đề: Brian Dean, 2013.