ông sau hành trình khám phá mê cung đã bị lạc, mê cung có dạng hình chữ nhật độ dài là ô, và độ rộng là ô, các ô trong mê cung là bằng nhau và có màu đỏ hoặc xanh, các ô trong mê cung có thể chứa phần thưởng hoặc không. ông sẽ xuất phát từ ô ở hàng , cột và đi xuống ô ở hàng , cột . Ở mỗi ô, ông có thể đi xuống dưới hoặc sang phải sao cho ông không vượt ra khỏi biên của mê cung. Sau khi đến ô ở hàng , cột ông sẽ vẽ lại đường đi của mình và lấy tất cả phần thưởng ở những ô màu xanh nằm ở phía dưới đường đi và tất cả phần thưởng ở những ô màu đỏ nằm phía trên đường đi, hiển nhiên ông cũng sẽ lấy tất cả phần thưởng nằm ở các ô nằm trên đường đi của mình nữa. Biết được rằng, trong mê cung có đúng ô có chứa phần thưởng .Nhiệm vụ của bạn là hãy tính tổng giá trị phần thưởng lớn nhất mà ông THA có thể đạt được.
Input
- Dòng đầu tiên ghi số lần lượt là số hàng, cột và số lượng ô chứa phần thưởng của mê cung()
- dòng tiếp theo, dòng thứ chứa số và kí tự biểu diễn ô thứ nằm trên hàng , cột và chứa phần thưởng có giá trị là và có màu là ( là ô màu đỏ, là ô màu xanh) (, , )
Output
- Gồm 1 số duy nhất là tổng phần thưởng lớn nhất mà ông nhận được.
Sample Input
Copy
1 10 10
1 1 954401907 B
1 2 188256336 B
1 3 463183048 B
1 4 89294440 B
1 5 502005835 R
1 6 198362921 R
1 7 687157907 R
1 8 698345596 R
1 9 280379131 R
1 10 245984334 R
Sample Output
Copy
4307371455
SUBTASK
- % số test có
- % số test còn lại không có ràng buộc gì
Bình luận