Sau khi vô địch AFF Cup 2018, đội tuyển bóng đá Việt Nam được một doanh nghiệp thưởng nóng bằng trò chơi bảng chứa vàng. Trong trò chơi, mỗi cầu thủ phải di chuyển trên một bảng hình chữ nhật , các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái qua phải. Ô ở hàng cột ghi số .
Mỗi cầu thủ được yêu cầu đi từ ô tới ô . Tại mỗi bước, cầu thủ chỉ được đi từ trên xuống dưới hoặc từ trái sang phải qua các ô kề cạnh, cứ đi qua ô nào (tính cả ô xuất phát và ô kết thúc), cầu thủ được nhận số vàng bằng số ghi trong trong ô đó.
Các cầu thủ vốn rất thông minh và tìm ra cách đi để đạt được số vàng tối đa được thưởng, tuy nhiên có một cổ động viên đối phương do cay cú nên muốn phá game. Anh ta gây sự bằng cách nhảy vào bảng chiếm trọn một ô, trừ ô xuất phát và ô kết thúc . Trong trường hợp cổ động viên quá khích này nhảy vào ô thì cầu thủ không lấy được vàng tương ứng với số điểm trong ô đó. Cổ động viên này muốn tìm một ô để ngồi chiếm sao cho trong chiến thuật tối ưu của mỗi cầu thủ, tổng số điểm lớn nhất có thể nhận được là tối thiểu.
Yêu cầu: Cho bảng với các giá trị . Với lượt đi của các cầu thủ biểu diễn bởi số . Hãy “an ủi” cổ động viên này bằng cách xác định tổng số vàng mà cầu thủ nhận được trong mỗi lượt nếu cổ động viên chọn được đúng ô tốt nhất có thể để chiếm theo mô tả trên.
Dữ liệu vào:
Dòng đầu tiên chứa ba số nguyên
dòng tiếp theo, dòng thứ chứa số nguyên
dòng cuối, mỗi dòng chứa bốn số nguyên dương
Dữ liệu ra:
Ghi ra dòng, dòng thứ chứa một số nguyên là số điểm mà cầu thủ nhận được ở lượt chơi thứ nếu cổ động viên xấu tính đó chọn được ô tốt nhất
Giới hạn:
số test có
số test khác có
số test còn lại có
Ví dụ:
Dữ liệu vào:
3 4 2
5 2 4 2
3 2 6 8
7 8 9 3
1 1 3 4
1 2 2 4
Dữ liệu ra:
28
16
Giải thích:
Trong ví dụ thứ nhất, chiếm ô . Trong ví dụ thứ hai, chiếm ô .
