I want to do conventional deadlifts

Interview

Time limit1sMemory limit1024 MB

Summary

Find the minimum sum of watchfulness values on a right-and-down path from the top-left to the bottom-right cell of a grid, then check whether it is at most H.

Level: Easy3 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

Jaehyeon is a beginner who believes he must do conventional deadlifts (lifting a barbell off the floor) to build his lower body. The biggest drawback of conventional deadlifts is noise. When the barbell is set back down, noise and vibration happen even with a platform. Strict gym regulars will not allow a skinny beginner like Jaehyeon to do conventional deadlifts, even in a gym where they are permitted. Help Jaehyeon do the lift without the regulars noticing.

The gym entrance is at the top left of an $N \times M$ grid map, at row 1, column 1. The barbell is at the bottom right, at row $N$ , column $M$ . Each cell may contain gym regulars, and each regular has a watchfulness value. Jaehyeon starts at the entrance and walks to the barbell. If the total watchfulness of the regulars he meets is greater than his stealth $H$ , he cannot do the deadlift. Meeting a regular means being in the same cell as that regular. Jaehyeon can move only right or down, and he cannot leave the map. Given $H$ , determine whether Jaehyeon can do the deadlift.

Input

The first line contains $N$ and $M$ . ( $1 \leq N, M \leq 1,000$ )

The next $N$ lines each contain $M$ integers describing the map. A $0$ is an empty cell, and a positive integer is the watchfulness of the gym regular in that cell.

The last line contains Jaehyeon's stealth $H$ .

Both the stealth and the watchfulness values are integers from $1$ to $100,000,000$ .

Output

If Jaehyeon can do the conventional deadlift, print "YES" on the first line. On the second line, print the minimum total watchfulness of the regulars he meets on the way to the barbell. Otherwise, print "NO".

Examples5

Example 1
Input
```
4 2
4 0
0 0
0 2
3 1
9
```
Expected output
```
YES
7
```
Example 2
Input
```
3 5
5 5 1 2 4
2 4 2 1 4
4 2 1 3 3
5
```
Expected output
```
NO
```

Example 3

Input

Expected output

NO

Example 4

Input

Expected output

YES
4

Example 5

Input

5 6
0 0 1 0 0 5
0 0 0 0 0 0
0 3 0 0 0 2
0 4 4 0 3 0
4 0 2 0 0 0
4

Expected output

YES
0