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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/hspc14h


 

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
2014-07-29 11:30:46 Kraken
Cái text phía trên lỗi anh ơi
2014-07-29 05:25:13 Lollipop
Dinh menh doc file sai, @@ cái đoạn cách trống
2014-07-28 10:06:42 Lollipop
test dưới 37 là sao nhỉ ??
2014-07-28 08:03:10 Nắng
đi thi đọc input sai @@@@

Last edit: 2014-07-28 08:05:58
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.