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.|

KCOLLECT - Thu hoạch

Công việc buôn bán dừa của Pirate không mấy khả quan cho lắm, khiến anh đêm ăn không ngon ngày ngủ không yên, chỉ biết chúi đầu vào xem "Rôbô trái cây". Một ngày nọ, đang nằm ngủ dưới gốc dừa, bỗng một trái dừa rơi vào đầu anh ấy. Cũng giống như Newton, Pirate cũng cầm trái dừa lên, ngắm nghía và... rủa: "Khỉ thật, sao xứ này toàn là dừa thế này!". Tức điên lên, Pirate quyết trồng thêm các loại trái cây khác vào hòn đảo của mình.

Đến mùa thu hoạch, Pirate đặt hàng một "Rôbô trái cây" để giúp mình hái quả. Khu vườn của Pirate có hình chữ nhật, và được chia thành M x N ô vuông bằng nhau. Trong mỗi ô vuông có một cây thuộc một loại quả khác nhau, đánh số từ 0 đến 9. Không phải vô tình mà chúng được đánh số như vậy, con số đó thể hiện giá trị kinh tế của các loại cây.

Tuy nhiên, nhìn mặt con Rôbô trái cây này có vẻ ngu ngu nên trong lần đầu tiên thử việc, Pirate muốn test AI của nó. Cụ thể là Rôbô phải tuân theo các quy định sau:

a. Tại mỗi ô, Rôbô chỉ có thể đi sang hướng đông hoặc hướng nam sang ô kề cạnh.

b. Có một số ô đặc biệt mà tại đó Rôbô có thể đi được thêm hướng tây hoặc hướng bắc sang ô kề cạnh (chỉ một trong hai).

c. Rôbô không được đi vào những ô có cây dừa (Pirate căm thù dừa).

d. Rôbô được đi qua một ô nhiều lần. Khi đi qua một ô, Rôbô phải hái hết quả ở cây trong ô đó. Lợi nhuận thu được sẽ bằng chỉ số của loại cây vừa được thu hái. Và sau này, không thể đạt thêm lợi nhuận gì từ ô đó nữa.

Xuất phát từ ô ở góc tây bắc của khu vườn, hãy giúp Rôbô trái cây xác định hành trình để đạt được lợi nhuận tối đa.

 

Input

  • Dòng thứ nhất: ghi hai số nguyên M và N - kích thước của khu vườn.
  • M dòng tiếp theo: mỗi dòng ghi N kí tự liên tiếp nhau mô tả khu vườn:

          + '0' - '9': các loại trái cây;

          + '#': cây dừa;

          + 'W': được quyền đi theo hướng tây;

          + 'N': được quyền đi theo hướng bắc.

Output

  • Ghi một số nguyên duy nhất là lợi nhuận tối đa đạt được.

Giới hạn

  • Trong mọi test, 1 ≤ M, N ≤ 100.
  • 60% số test có 1 ≤ M, N ≤ 20.

Example

Input:
2 3
264
3WW

Output: 15

Giải thích: Rôbô sẽ đi theo hành trình như sau (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (2, 2) -> (2, 1) (ô (i, j) là ô ở dòng i và cột j). Tổng lợi nhuận sẽ là 2 + 6 + 4 + 3 = 15.


Được gửi lên bởi:Nguyễn Xuân Khánh
Ngày:2011-07-10
Thời gian chạy:0.200s
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

hide comments
2019-07-13 18:42:04
sap xep topo 1 dam AC oh yeahhhh =>>>>
2017-08-21 08:42:53 Ðặng Minh Tiến
https://kienthuc24h.com/kcollect-spoj-thu-hoach/
2012-12-15 14:18:11 kệ anh chứ
TPLT+TOPO
2011-08-17 12:02:43 nguyen van dung
bia nax hay ghe
2011-07-11 18:13:21 Noyethug


Last edit: 2012-02-07 14:17:20
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.