Bài tập

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\).

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) loại vàng, mỗi loại có số lượng không giới hạn. Một thỏi vàng loại \(i\) nặng \(w_i\) và có giá trị \(v_i\). Người anh mang theo một chiếc túi chịu được tổng trọng lượng tối đa \(M\).

Hãy tìm tổng giá trị lớn nhất có thể mang đi, biết rằng mỗi loại có thể lấy bao nhiêu thỏi tuỳ ý (kể cả không lấy) và tổng trọng lượng không vượt quá \(M\).

Input

• Dòng đầu chứa hai số nguyên \(M\) và \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(v_i\) và \(w_i\): giá trị và trọng lượng của một thỏi loại \(i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 500\)
• \(1 \le M \le 2 \cdot 10^6\)
• \(1 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^9\)
• \(N \cdot \sum_{i=1}^{N} \max(0,\, M - w_i) \le 10^8\) (các loại nặng hơn \(M\) không đóng góp vào tổng này).

Sample Input

13 3
6 4
5 3
9 5

Sample Output

23

Explanation

Chọn \(2\) thỏi loại 3 (nặng \(10\), giá trị \(18\)) và \(1\) thỏi loại 2 (nặng \(3\), giá trị \(5\)): tổng nặng \(13\), giá trị \(23\). Đây là phương án tốt nhất.

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) hòn vàng. Hòn vàng thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Người anh mang theo một chiếc túi chịu được tổng trọng lượng tối đa \(M\), mỗi hòn vàng chỉ có thể lấy tối đa một lần.

Hãy tìm tổng giá trị lớn nhất của các hòn vàng mà người anh có thể bỏ vào túi mà tổng trọng lượng không vượt quá \(M\).

Input

• Dòng đầu chứa hai số nguyên \(M\) và \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(v_i\) và \(w_i\): giá trị và trọng lượng của hòn vàng thứ \(i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 500\)
• \(1 \le M \le 2 \cdot 10^6\)
• \(0 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^9\)
• \(N \cdot \sum_{i=1}^{N} \max(0,\, M - w_i) \le 10^8\) (các hòn vàng nặng hơn \(M\) không đóng góp vào tổng này).

Sample Input

12 4
6 3
9 7
5 4
13 9

Sample Output

19

Explanation

Chọn hòn 2 và hòn 3 (nặng \(7+4=11 \le 12\)) được giá trị \(14\); chọn hòn 1 và hòn 4 (nặng \(3+9=12\)) được \(19\); chọn hòn 1, 2 (nặng \(10\)) được \(15\). Kết quả tốt nhất là \(19\).