Năng lượng mặt trời là một trong những nguồn năng lượng xanh mang lại vô số lợi ích cho cả nền kinh tế và môi trường. Tuy nhiên hiện nay năng lượng mặt trời vẫn chưa được áp dụng rộng rãi. Bạn là trưởng ban năng lượng của thành phố Mondstadt và được nhận nhiệm vụ thí điểm sử dụng năng lượng mặt trời ở một số hộ gia đình. Bản đồ thành phố Mondstadt có dạng hình chữ nhật gồm
Input
- Dòng đầu tiên là một số nguyên dương
là số lượng bộ test. - Dòng đầu tiên của mỗi bộ test là 3 số nguyên dương
. dòng tiếp theo, mỗi dòng gồm số nguyên dương , là chi phí hộ gia đình ở vị trí hàng cột phải trả nếu sử dụng năng lượng mặt trời.- Dòng tiếp theo là
, số lượng khu vực trọng điểm. dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương lần lượt là vị trí của ô trái trên và ô phải dưới của các khu vực.
Output
- Gồm
dòng, mỗi dòng in ra một số duy nhất là chênh lệch bé nhất tìm được trong phương án tối ưu
Sample input
2
3 4 2
1 8 7 7
6 1 7 6
4 3 4 2
2
1 2 2 3
2 1 3 2
3 4 3
1 8 7 7
6 1 7 6
4 3 4 2
2
1 2 2 3
2 1 3 2
Sample output
0
1
Giải thích
- Ở ví dụ đầu tiên, chọn hộ gia đình ở ô
và ô là phương án tối ưu. Khi đó khu vực thứ nhất có mức độ phủ năng lượng là 2, khu vực thứ hai có mức độ phủ năng lượng là 0 - Ở ví dụ thứ hai, chọn hộ gia đình ở ô
và ô là phương án tối ưu. Khi đó khu vực thứ nhất có mức độ phủ năng lượng là 3, khu vực thứ hai có mức độ phủ năng lượng là 0
Tính điểm
- Subtask 1: 30% số test có
, - Subtask 2: 30% số test có
- Subtask 3: 40% số test có
Comments