Bài tập

Tèo biến đổi một số nguyên dương theo quy tắc: nếu chữ số cuối cùng khác \(0\) thì trừ số đó đi \(1\); nếu chữ số cuối cùng bằng \(0\) thì bỏ chữ số đó đi (chia số cho \(10\)).

Cho số \(n\), Tèo thực hiện phép biến đổi đúng \(k\) lần liên tiếp. In ra số thu được. Dữ liệu đảm bảo kết quả cuối cùng là số nguyên dương.

Input

Một dòng gồm hai số nguyên \(n\) và \(k\).

Output

Số thu được sau \(k\) lần biến đổi.

Constraints

• \(2 \le n \le 10^9\)
• \(1 \le k \le 50\)

Sample Input

2350 5

Sample Output

231

Explanation

\(2350 \to 235 \to 234 \to 233 \to 232 \to 231\).

Tuổi hiện tại của bố Tí là \(F\) và của Tí là \(T\). Sau bao nhiêu năm nữa thì tuổi bố đúng bằng hai lần tuổi Tí? (Nếu hiện tại đã đúng như vậy thì đáp án là \(0\).)

Input

Một dòng gồm hai số nguyên \(F\) và \(T\).

Output

Số năm cần chờ.

Constraints

• \(1 \le T\), \(2T \le F \le 10^9\)

Sample Input 1

27 9

Sample Output 1

9

Sample Input 2

64 32

Sample Output 2

0

Một khu mỏ trên Sao Hỏa có dạng lưới gồm \(n\) hàng và \(m\) cột. Ô \((i, j)\) chứa \(y_{i,j}\) đơn vị quặng yeyenum và \(b_{i,j}\) đơn vị quặng bloggium. Nhà máy luyện yeyenum nằm sát mép tây (bên trái) của lưới, còn nhà máy luyện bloggium nằm sát mép bắc (phía trên) của lưới.

Trong mỗi ô ta phải lắp đúng một trong hai loại băng tải:

• băng tải hướng tây: chuyển quặng yeyenum của ô đó sang trái;
• băng tải hướng bắc: chuyển quặng bloggium của ô đó lên trên.

Quặng phải đi thẳng đến nhà máy mà không được rẽ. Vì vậy quặng yeyenum của ô \((i, j)\) chỉ đến được nhà máy nếu mọi ô \((i, 1), (i, 2), \dots, (i, j)\) đều dùng băng tải hướng tây. Tương tự, quặng bloggium của ô \((i, j)\) chỉ đến được nhà máy nếu mọi ô \((1, j), (2, j), \dots, (i, j)\) đều dùng băng tải hướng bắc. Quặng không đến được đúng nhà máy của nó thì bị mất, và loại quặng còn lại trong cùng một ô không được khai thác (mỗi ô chỉ khai thác loại tương ứng với băng tải của nó).

Hãy chọn loại băng tải cho từng ô để tổng lượng quặng đến được nhà máy là lớn nhất.

Input

Input gồm nhiều bộ test. Mỗi bộ test:

• Dòng đầu chứa hai số nguyên \(n\) và \(m\).
• \(n\) dòng tiếp theo, mỗi dòng \(m\) số nguyên: các giá trị \(y_{i,j}\).
• \(n\) dòng tiếp theo, mỗi dòng \(m\) số nguyên: các giá trị \(b_{i,j}\).

Input kết thúc bằng một dòng có \(n = m = 0\) (không xử lý bộ test này).

Output

Với mỗi bộ test, in ra một dòng: tổng lượng quặng lớn nhất có thể khai thác.

Constraints

• \(1 \le n, m \le 500\)
• \(0 \le y_{i,j}, b_{i,j} \le 1000\)

Sample Input

2 3
2 0 7
5 1 0
3 3 0
1 9 4
1 1
4
1
3 2
0 6
2 2
8 0
5 1
0 7
3 3
0 0

Sample Output

24
4
26

Explanation

Ở bộ test thứ hai (lưới \(1 \times 1\)), chọn băng tải hướng tây thu được \(4\), lớn hơn \(1\) của hướng bắc.

Một cửa hàng kẹo có một thanh kẹo dài \(N\) cm, được ghép từ \(N\) đoạn dài \(1\) cm. Mỗi đoạn là ngọt (ký hiệu 1) hoặc chua (ký hiệu 0). Người bán có thể bẻ thanh kẹo tại các mối nối giữa hai đoạn liên tiếp để chia nó thành nhiều mẩu liên tiếp (có thể không bẻ chỗ nào, cũng có thể bẻ tại mọi mối nối).

Khách hàng nhỏ tuổi chỉ chịu mua một mẩu nếu trong mẩu đó số đoạn ngọt nhiều hơn hẳn số đoạn chua. Những mẩu không được mua sẽ bị bỏ lại.

Hãy cho biết tổng chiều dài lớn nhất của các mẩu bán được, nếu người bán bẻ thanh kẹo một cách tối ưu.

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng thứ nhất chứa số nguyên \(N\); dòng thứ hai chứa xâu gồm \(N\) ký tự 0 hoặc 1 mô tả thanh kẹo từ trái sang phải.

Output

Với mỗi bộ dữ liệu in ra một số nguyên là tổng chiều dài lớn nhất bán được.

Constraints

• \(1 \le t \le 100\)
• \(1 \le N \le 200\)

Sample Input

3
8
11010100
5
00100
11
01110010011

Sample Output

7
1
11

Explanation

Ở bộ thứ nhất, cả thanh có \(4\) đoạn ngọt và \(4\) đoạn chua nên không bán nguyên được; bẻ bỏ đoạn cuối cùng thì mẩu 1101010 (4 ngọt, 3 chua) bán được, dài \(7\). Ở bộ thứ hai chỉ bán được mẩu 1 (dài \(1\)). Ở bộ thứ ba, cả thanh có \(7\) đoạn ngọt và \(4\) đoạn chua nên bán nguyên thanh, được \(11\).