레이팅 미적용농부 존은 자기가 소를 몇 마리 가지고 있는지 완전히 잊어버렸다! 그는 밭에 마이크를 몰래 설치해 소의 수를 세기로 했다. 들리는 모든 울음소리의 총 음량으로부터 소의 수를 알아낼 수 있으리라 생각한 것이다.
FJ의 N개의 밭(1 <= N <= 100)은 길고 곧은 도로를 따라 일렬로 늘어서 있다. FJ는 B개의 서로 다른 품종(1 <= B <= 20)의 소를 기르는데, 품종 i의 소는 음량 V(i)(1 <= V(i) <= 100)로 운다. 도로를 따라 강한 바람이 불어 울음소리를 왼쪽에서 오른쪽으로 실어 나른다: 어떤 밭의 총 울음 음량이 X라면, 다음 밭의 총 울음 음량에 X-1만큼 기여한다(그 다음 밭에는 X-2, 이런 식이다). 한 밭의 울음 음량은 그 밭에 있는 소들이 내는 기여분에, 앞 밭의 총 울음 음량이 X일 때 X-1을 더한 값이다.
FJ가 각 밭에서 기록한 울음 음량이 주어질 때, FJ가 가질 수 있는 소의 최소 수를 계산하라. 어느 밭에서든 기록된 음량은 최대 100,000이다.
첫째 줄: 정수 N과 B가 주어진다.
둘째 줄부터 1+B째 줄까지: i+1째 줄에는 정수 V(i)가 주어진다.
2+B째 줄부터 1+B+N째 줄까지: 1+B+i째 줄에는 밭 i의 모든 울음의 총 음량이 주어진다.
FJ가 가진 소의 최소 수를 출력한다. 입력과 일치하는 소의 배치가 없으면 -1을 출력한다.
mooomoo.in · 출력을 쓸 파일 mooomoo.out5 2
5
7
0
17
16
20
194Output details: There are 2 cows of breed #1 and 1 cow of breed #2 in field 2, and another cow of breed #1 in field 4.