Không Thối Tiền

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\le K\le 16$
• $1\le N\le 100000$
• Mệnh giá đồng xu: $1\le c_i\le {10}^8$
• Chi phí giao dịch: $1\le p_j\le 10000$

Ví dụ