Bài tập

Một chiếc bánh kem hình tròn (nhìn từ trên xuống) đã bị cắt sẵn \(n\) nhát. Mỗi nhát cắt là một đoạn thẳng đi từ tâm bánh ra tới mép bánh; nhát thứ \(i\) hợp với tia \(Ox\) (chiều dương) một góc \(a_i\) độ. Các góc được liệt kê theo chiều ngược chiều kim đồng hồ và không giảm, nên có thể có nhiều nhát cắt trùng nhau (khi đó chúng chỉ được tính là một nhát cắt duy nhất).

Các nhát cắt chia chiếc bánh thành các miếng hình quạt: mỗi miếng nằm giữa hai nhát cắt kề nhau (kể cả cặp nhát cuối và nhát đầu quay vòng lại). Cần cắt thêm một số nhát (cũng là các đường từ tâm ra mép, ở góc tùy ý) sao cho tất cả các miếng bánh đều có góc bằng nhau.

Hãy tính số nhát cắt thêm ít nhất cần thực hiện.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

Output

• In ra một số nguyên: số nhát cắt thêm ít nhất.

Constraints

• \(1 \le n \le 10\)
• \(0 \le a_i \le 359\)
• \(a_i \le a_{i+1}\)

Sample Input 1

3
0 90 120

Sample Output 1

9

Sample Input 2

2
10 190

Sample Output 2

0

Explanation

Ví dụ 1: các nhát cắt ở 0, 90 và 120 độ tạo các miếng 90, 30 và 240 độ. Góc miếng nhỏ nhất có thể chia đều là ước chung lớn nhất của các góc này và 360, tức 30 độ, tổng cộng 12 miếng. Đã có 3 nhát nên cần thêm 9 nhát.

Ví dụ 2: hai nhát tạo hai miếng 180 độ bằng nhau, không cần cắt thêm.

Bạn Minh gặp một "đẳng thức" sai có dạng \(A = S\), trong đó \(A\) và \(S\) là hai số nguyên dương viết bằng chữ số thập phân, không có chữ số \(0\) đứng đầu, và \(A \ne S\). Để sửa lại cho đúng, Minh được phép chèn thêm các dấu cộng + vào giữa một số cặp chữ số liền nhau của \(A\), sao cho tổng các số hạng thu được đúng bằng \(S\). Các số hạng sau khi tách có thể có chữ số \(0\) đứng đầu (ví dụ 05 được hiểu là \(5\), 000 là \(0\)).

Hãy tìm số dấu cộng ít nhất cần chèn.

Input

Một dòng duy nhất có dạng A=S (không có dấu cách). Dữ liệu đảm bảo luôn tồn tại ít nhất một cách chèn.

Output

In ra số dấu cộng tối thiểu cần chèn.

Constraints

• \(A\) có tối đa \(1000\) chữ số.
• \(1 \le S \le 5000\).

Sample Input

3120405=96

Sample Output

3

Explanation

Chèn thành 31+20+40+5 có tổng \(96\) với \(3\) dấu cộng. Không thể dùng ít hơn \(3\) dấu cộng.

Kỳ thi chọn đội tuyển có \(K\) bài tập và \(N\) giám khảo. Giám khảo thứ \(i\) đề nghị cho bài thứ \(j\) số điểm \(A[i][j]\).

Hội đồng cần gán cho mỗi bài một số điểm \(b_1, b_2, \dots, b_K\) thỏa mãn đồng thời:

• Tổng điểm \(b_1 + b_2 + \dots + b_K\) đúng bằng \(S\).
• Điểm không giảm theo thứ tự bài: \(b_1 \le b_2 \le \dots \le b_K\).
• Với mỗi bài \(j\), điểm \(b_j\) phải bằng số điểm mà một giám khảo nào đó đề nghị cho bài \(j\) (tức \(b_j = A[i][j]\) với một \(i\) nào đó).

Hãy tìm một cách gán điểm hợp lệ. Nếu có nhiều cách, in cách có dãy \((b_1, b_2, \dots, b_K)\) nhỏ nhất theo thứ tự từ điển.

Input

• Dòng đầu gồm ba số nguyên \(S, N, K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(K\) số nguyên \(A[i][1], \dots, A[i][K]\).

Output

• Nếu không có cách gán nào, in NO.
• Ngược lại in YES ở dòng đầu, dòng thứ hai in \(K\) số \(b_1, \dots, b_K\) cách nhau một dấu cách.

Constraints

• \(1 \le S \le 200\), \(1 \le N \le 20\), \(1 \le K \le 20\)
• \(0 \le A[i][j] \le 200\)

Sample Input 1

24 3 3
4 7 10
6 5 12
3 9 8

Sample Output 1

YES
3 9 12

Sample Input 2

10 3 2
1 2
3 4
2 1

Sample Output 2

NO

Explanation

Ở ví dụ 1, điểm bài 1 lấy từ \(\{4,6,3\}\), bài 2 từ \(\{7,5,9\}\), bài 3 từ \(\{10,12,8\}\). Cách \(3, 9, 12\) có tổng \(24\) và không giảm. Ở ví dụ 2, tổng lớn nhất có thể là \(3+4=7<10\) nên không có cách nào.

Cô giáo đưa cho hai bạn Nam và Bình một xâu \(s\) chỉ gồm các chữ số \(0\)–\(9\) và đặt bài toán: hãy cắt xâu thành đúng \(K\) đoạn liên tiếp (mỗi đoạn không rỗng, mỗi ký tự thuộc đúng một đoạn) sao cho giá trị số của mỗi đoạn không vượt quá \(Z\). Đoạn được hiểu là số nguyên thập phân và có thể có chữ số \(0\) ở đầu (ví dụ 07 có giá trị \(7\)).

Trong tất cả các cách cắt hợp lệ, hãy chọn cách sao cho tổng giá trị của \(K\) đoạn là lớn nhất. Nếu không có cách cắt nào hợp lệ, in ra \(-1\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa hai số nguyên \(K\) và \(Z\); dòng thứ hai chứa xâu \(s\).

Output

Với mỗi bộ test in ra một dòng là tổng lớn nhất, hoặc \(-1\) nếu không thể cắt.

Constraints

• \(1 \le T \le 10\)
• \(1 \le K \le 100\), \(1 \le Z \le 10^9\)
• \(1 \le |s| \le 100\), \(s\) chỉ gồm các ký tự từ 0 đến 9

Sample Input

3
2 50
4817
1 20
123
3 100
90210

Sample Output

65
-1
111

Explanation

Bộ test 1: cắt 48|17, tổng \(65\). Bộ test 2: chỉ có thể lấy cả xâu là \(123 > 20\) nên không hợp lệ. Bộ test 3: cắt 90|21|0, tổng \(111\).