Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HSPC14H - Táo chuối

 

Cư dân của hai làng cạnh nhau (gọi làng A và B) không thể giải quyết tranh chấp đất đai. Khu
vực tranh chấp là hình chữ nhật, bao gồm R×C ô đất. Mỗi ô có hoặc một số cây táo hay một số
cây chuối trong đó.
Một cố vấn nước ngoài được yêu cầu hòa giải tranh chấp. Ông quyết định cho một xe ủi đất đi
qua khu vực này và chặt bỏ tất cả các cây trong các ô mà xe đi qua. Xe ủi đất sẽ bắt đầu ở góc
trên bên trái của khu vực và luôn luôn di chuyển theo một trong ba hướng: sang phải, xuống
dưới, hoặc chéo xuống dưới bên phải. Xe ủi dừng lại khi đến góc dưới bên phải.
Làng A sẽ nhận được khu đất bên dưới con đường đất, trong khi làng B sẽ nhận được khu đất
bên trên nó. Lưu ý rằng ngôi làng có thể không nhận được ô đất nào
Người cố vấn nhận thấy rằng người dân làng A thích táo, còn người dân làng B thích chuối. Vì
vậy, ông quyết định lựa chọn con đường đất sao cho số lượng cây táo bên dưới con đường và

Cư dân của hai làng cạnh nhau (gọi làng A và B) không thể giải quyết tranh chấp đất đai. Khu vực tranh chấp là hình chữ nhật, bao gồm R×C ô đất. Mỗi ô có hoặc một số cây táo hay một số cây chuối trong đó.

Một cố vấn nước ngoài được yêu cầu hòa giải tranh chấp. Ông quyết định cho một xe ủi đất đi qua khu vực này và chặt bỏ tất cả các cây trong các ô mà xe đi qua. Xe ủi đất sẽ bắt đầu ở góc trên bên trái của khu vực và luôn luôn di chuyển theo một trong ba hướng: sang phải, xuống dưới, hoặc chéo xuống dưới bên phải. Xe ủi dừng lại khi đến góc dưới bên phải.

Làng A sẽ nhận được khu đất bên dưới con đường đất, trong khi làng B sẽ nhận được khu đất bên trên nó. Lưu ý rằng ngôi làng có thể không nhận được ô đất nào. Người cố vấn nhận thấy rằng người dân làng A thích táo, còn người dân làng B thích chuối. Vì vậy, ông quyết định lựa chọn con đường đất sao cho số lượng cây táo bên dưới con đường và những số lượng cây chuối bên trên con đường lớn nhất có thể. Viết một chương trình tính toán tổng số lượng cực đại này.

 

Input

Dòng đầu tiên ghi số nguyên R và C (2 ≤ R, C ≤ 1500), kích thước của khu vực. Mỗi dòng trong N dòng tiếp theo chứa C mô tả về các ô đất. Mỗi mô tả bao gồm chữ 'A' (táo) hoặc 'B' (chuối) và số cây tương ứng trong một ô. Mỗi ô chứa từ 1 đến 99 cây.

Output

In ra tổng số lượng cây lớn nhất như mô tả ở trên.

Example

Input:
4 3
B2 B3 B5
A3 B1 A1
A2 A4 B1
B1 B3 A3

Output:
17
Input:
3 5
A5 A2 B3 A6 B2
A1 B20 A5 B3 B6
A3 A5 B3 B8 A3

Output:
37

Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-07-27
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSPC 2014

hide comments
2017-06-21 11:57:11
https://onlylove97.wordpress.com/2014/09/02/hspc14h-spoj/
2015-09-14 17:21:19
Tham khảo thuật toán : http://baitapspoj.blogspot.com/2015/09/HSPC14H.html
2015-05-28 14:04:54 there's no salvation for me...
chú ý phần nhập nhé
2015-05-28 14:04:54 there's no salvation for me...
chú ý phần nhập nhé
2014-08-11 13:34:42 LOVE VNOI
test chính xác là:
4 3
B2 B3 B5
A3 B1 A1
A2 A4 B1
B1 B3 A3

17



3 5
A5 A2 B3 A6 B2
A1 B20 A5 B3 B6
A3 A5 B3 B8 A3

37


Last edit: 2014-08-11 14:11:21
2014-08-01 20:37:06 Thcs Ðặng Chánh Kỷ
bài này qhd bình thường mà đâu có khó chỉ ke mỗi đọc file
2014-08-01 20:35:22 Thcs Ðặng Chánh Kỷ
ke bài này thật, mãi mới ac được do đọc file sai làm mình mất gần 1 đêm, ngu quá

Last edit: 2014-08-01 20:35:44
2014-07-31 10:12:00 Kraken
rank 1=)) cầu mong đừng bác nào vượt =))
2014-07-29 11:42:24 Tây Cuồng
không hiểu cái test? ai cho mình xin test đúng với
2014-07-29 11:30:46 Kraken
Cái text phía trên lỗi anh ơi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.