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(1n,m,k105)
  • 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) (1xn, 1ym, 1z109)

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

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

  • 40% số test có 1n,m10
  • 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.