Bài toán Robot di chuyển trên một ma trận.

Cho một ma trận NxM ô, mỗi ô chứa thông tin như sau:

0: ô có thể đi đến

#: ô không thể đi đến

x: được cộng thêm x năng lượng.

-x: bị giảm thêm x năng lượng.

(với x là 1 số nguyên dương từ 1 đến 100)

Một con robot có thể di chuyển theo hướng đi qua phải, hoặc đi xuống (mỗi lần đi một ô). Ban đầu robot có K năng lượng dùng để di chuyển, mỗi lần di chuyển sang một ô năng lượng sẽ giảm đi 1 (đơn vị). Nếu năng lượng của robot bằng 0 thì sẽ không di chuyển được.

Yêu cầu là hãy xác định xem robot có thể di chuyển từ vị trí A có thể đến được vị trí B hay không? Nếu có xuất YES và năng lượng còn lại, ngược lại xuất NO.

Nếu có nhiều phương án, hãy xuất phương án có năng lượng còn lại là lớn nhất.

Input: nhập từ file robot.inp

-         Dòng 1: Chứa 3 số N, M và K

-         Dòng 2: chứa tọa độ A

-         Dòng 3 chứa tọa độ B

-         N dòng tiếp theo, mỗi dòng chứ M số (hoặc dấu #) (mỗi số là 1 trong 3 số 0, x, -x hoặc #), mỗi số cách nhau 1 khoảng cách

Output: xuất ra file robot.out

-         Xuất NO nếu robot không đến được B ngược lại xuất YES và năng lượng còn lại.

Lưu ý: ma trận được đánh số dòng từ 0 đến N-1, cột từ 0 đến M-1.

Ví dụ: