Bài tập

Cho bảng số nguyên \(a\) gồm \(m\) hàng và \(n\) cột. Tính tổng các phần tử của từng hàng và in ra giá trị tổng lớn nhất trong các hàng.

Input

• Dòng đầu: hai số nguyên \(m, n\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên là các phần tử của một hàng.

Output

• Một số nguyên: tổng lớn nhất của một hàng.

Constraints

• \(1 \le m, n \le 500\)
• \(|a_{ij}| \le 10^6\)

Sample Input

2 4
5 1 -3 2
-1 8 0 4

Sample Output

11

Explanation

Tổng hàng 1 là \(5\), tổng hàng 2 là \(11\); lớn nhất là \(11\).

Với số nguyên không âm \(n\), quy trình GSUM như sau: thay \(n\) bằng tổng các chữ số của nó, lặp lại cho tới khi kết quả chỉ còn đúng một chữ số; chữ số đó là \(\mathrm{GSUM}(n)\). Ví dụ \(\mathrm{GSUM}(9876)\): \(9+8+7+6 = 30\), rồi \(3+0 = 3\), nên \(\mathrm{GSUM}(9876) = 3\).

Hãy viết hàm đệ quy tính \(\mathrm{GSUM}(n)\) (với \(n\) đã là một chữ số thì kết quả là chính \(n\)).

Input

Một số nguyên \(n\).

Output

In ra \(\mathrm{GSUM}(n)\).

Constraints

• \(0 \le n \le 10^{18}\)

Sample Input 1

9876

Sample Output 1

3

Sample Input 2

88

Sample Output 2

7

Explanation

Ở ví dụ 2: \(8 + 8 = 16\), rồi \(1 + 6 = 7\).

Cho dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) và một số nguyên \(K\). Một thao tác gộp chọn hai phần tử bất kỳ của dãy, xoá cả hai và thay bằng một phần tử mới có giá trị bằng tổng của chúng (vị trí đặt phần tử mới không quan trọng).

Sau khi thực hiện một số lượng tuỳ ý các thao tác gộp (có thể không thực hiện thao tác nào), hãy tìm số lượng lớn nhất các phần tử của dãy chia hết cho \(K\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, \dots, A_N\).

Output

• Một số nguyên duy nhất: số phần tử chia hết cho \(K\) nhiều nhất có thể đạt được.

Constraints

• \(1 \le N \le 10^5\)
• \(K \in \{4, 5\}\)
• \(1 \le A_i < 10^6\)

Phân bố điểm:

• \(30\%\) số test: \(N \le 10^3\), \(K = 4\).
• \(30\%\) số test: \(N \le 10^3\), \(K = 5\).
• \(40\%\) số test: \(N \le 10^5\), \(K = 4\) hoặc \(K = 5\).

Sample Input

7 4
5 6 7 9 2 3 10

Sample Output

3

Explanation

Số dư khi chia cho \(4\) lần lượt là \(1, 2, 3, 1, 2, 3, 2\). Gộp \(5+7=12\), \(9+3=12\), \(6+2=8\); dãy còn \(12, 12, 8, 10\) có \(3\) phần tử chia hết cho \(4\). Không thể đạt \(4\).

Cho một bảng chữ cái gồm \(M\) dòng và \(N\) cột, mỗi ô chứa một chữ cái in hoa. Xuất phát từ một ô tuỳ chọn, bạn được di chuyển liên tiếp sang một ô chung cạnh (trên, dưới, trái, phải) và ghi lại chữ cái của mọi ô đã đi qua. Điều kiện: chữ cái của ô sau phải lớn hơn hẳn chữ cái của ô ngay trước nó theo thứ tự bảng chữ cái (A < B < ... < Z). Vì vậy không ô nào bị đi qua hai lần.

Chẳng hạn có thể đi theo dãy chữ A, B, D, F nhưng không thể đi theo A, B, B hay C, B, A.

Hãy tìm độ dài lớn nhất (số ô) của một đường đi hợp lệ.

Input

• Dòng 1: hai số nguyên \(M\), \(N\).
• \(M\) dòng sau, mỗi dòng là một xâu gồm \(N\) chữ cái in hoa.

Output

In ra một số nguyên: độ dài đường đi dài nhất.

Constraints

• \(1 \le M, N \le 20\)

Sample Input 1

3 3
ABC
BCD
DEF

Sample Output 1

5

Sample Input 2

3 4
DCBA
EGHB
FBCD

Sample Output 2

7

Explanation

Ở ví dụ 1, một đường đi dài nhất là A(1,1) -> B(2,1) -> C(2,2) -> E(3,2) -> F(3,3) gồm 5 ô; không có đường nào dài hơn.