Farmer John đã hoàn toàn quên mất mình sở hữu bao nhiêu con bò! Ông quá xấu hổ để ra đồng đếm vì không muốn những cô bò nhận ra sự đãng trí của mình. Thay vào đó, ông quyết định bí mật đếm bò bằng cách đặt micrô tại những cánh đồng nơi chúng thường tụ tập, với suy luận rằng có thể xác định số bò từ tổng âm lượng của tất cả tiếng rống nghe được.

\(N\) cánh đồng của FJ (\(1 \le N \le 100\)) nằm thành một hàng dọc theo một con đường thẳng dài. Mỗi cánh đồng có thể chứa nhiều giống bò; FJ sở hữu bò thuộc \(B\) giống khác nhau (\(1 \le B \le 20\)), và một cô bò giống \(i\) rống với âm lượng \(V(i)\) (\(1 \le V(i) \le 100\)). Hơn nữa, một luồng gió mạnh thổi dọc con đường, mang âm thanh theo một hướng từ trái sang phải: nếu âm lượng tiếng rống trong một cánh đồng là \(X\), âm thanh này sẽ đóng góp \(X-1\) vào tổng âm lượng tiếng rống ở cánh đồng kế tiếp (rồi \(X-2\) ở cánh đồng sau nữa, v.v.). Nói cách khác, âm lượng tiếng rống tại một cánh đồng bằng tổng đóng góp của những cô bò trong chính cánh đồng đó cộng với \(X-1\), trong đó \(X\) là tổng âm lượng tiếng rống tại cánh đồng ngay trước.

Cho âm lượng tiếng rống mà FJ ghi lại tại mỗi cánh đồng, hãy tính số bò ít nhất mà FJ có thể sở hữu.

Âm lượng FJ ghi lại tại bất kỳ cánh đồng nào cũng không vượt quá \(100\,000\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\).
• \(B\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(V(i)\).
• \(N\) dòng cuối, dòng thứ \(i\) chứa tổng âm lượng của tất cả tiếng rống tại cánh đồng \(i\).

Ràng buộc

• \(1 \le N \le 100\).
• \(1 \le B \le 20\).
• \(1 \le V(i) \le 100\).
• Âm lượng ghi lại tại mỗi cánh đồng không vượt quá \(100\,000\).

Dữ liệu ra

In ra số bò ít nhất mà FJ sở hữu, hoặc \(-1\) nếu không tồn tại cách bố trí bò nào phù hợp với dữ liệu vào.

Ví dụ

5 2
5
7
0
17
16
20
19

4

Nguồn

USACO 2014 March Contest, Silver — Mooo Moo

Tác giả: Brian Dean, 2014.