Tiếng Bò Kêu

Đ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

Có $N$ cánh đồng xếp thành hàng ngang và $B$ giống bò khác nhau. Giống bò thứ $i$ tạo ra tiếng kêu có âm lượng $V (i)$ .

Âm thanh lan truyền sang phải với cường độ giảm dần: nếu một cánh đồng tạo ra tổng âm lượng $X$ , thì cánh đồng kế tiếp nhận được $X - 1$ , cánh đồng sau đó nhận $X - 2$ , v.v. (giảm đến 0 thì dừng).

Cho tổng âm lượng ghi nhận tại mỗi cánh đồng, hãy tìm số lượng bò tối thiểu có thể tạo ra các âm lượng đó, hoặc in $- 1$ nếu không thể.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $B$ .
$B$ dòng tiếp theo: âm lượng $V (i)$ của từng giống bò.
$N$ dòng tiếp theo: tổng âm lượng ghi nhận tại mỗi cánh đồng.

Dữ liệu ra

Một số nguyên duy nhất — số bò tối thiểu, hoặc $- 1$ nếu không thể.

Ràng buộc

$1 \leq N \leq 100$
$1 \leq B \leq 20$
$1 \leq V (i) \leq 100$
Tổng âm lượng tại mỗi cánh đồng $\leq 100 000$

Ví dụ

Input	Output	Giải thích
5 2 5 7 0 17 16 20 19	4	Đặt 2 bò giống 1 và 1 bò giống 2 ở cánh đồng 2 (âm lượng = $5 + 5 + 7 = 17$ ), và 1 bò giống 1 ở cánh đồng 4 (âm lượng = $5$ ). Tổng cộng 4 bò.

Bình luận

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