Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
THA
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

ông ~THA~ sau hành trình khám phá mê cung đã bị lạc, mê cung có dạng ~1~ hình chữ nhật độ dài là ~n~ ô, và độ rộng là ~m~ ô, 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 ~THA~ sẽ xuất phát từ ô ở hàng ~1~, cột ~1~ và đi xuống ô ở hàng ~n~, cột ~m~. Ở 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 ~n~, cột ~m~ ô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 ~k~ ô 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ố ~n, m, k~ lần lượt là số hàng, cột và số lượng ô chứa phần thưởng của mê cung(~1 \le n, m, k \le 10^5~)
  • ~k~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số ~x, y, z~ và kí tự ~c~ biểu diễn ô thứ ~i~ nằm trên hàng ~x~, cột ~y~ và chứa phần thưởng có giá trị là ~z~ và có màu là ~c~ (~R~ là ô màu đỏ, ~B~ là ô màu xanh) (~1 \le x \le n~, ~1 \le y \le m~, ~1 \le z \le 10^9~)

Output

  • Gồm 1 số duy nhất là tổng phần thưởng lớn nhất mà ông ~THA~ nhận được.

Sample Input

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

4307371455

SUBTASK

  • ~40~% số test có ~1 \le n, m \le 10~
  • ~60%~% số test còn lại không có ràng buộc gì

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.