J. Trade
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a prosperous country, Kingsnow decided to engage in trade.

The country consists of $$$n*m$$$ cities. Each city is represented by an integer pair $$$(x, y)$$$, where $$$1\leq x\leq n$$$ and $$$1\leq y\leq m$$$, indicating its position in a grid. In city $$$(x,y)$$$, the item's price is denoted by $$$a[x][y]$$$, and the travel expense to reach this city is denoted by $$$b[x][y]$$$.

Before embarking on his journey, Kingsnow needs you to plan a route for him. The route must meet the following criteria:

  • The route must start at the city located at the first row and first column, i.e., $$$(1, 1)$$$.
  • The route must end at a city located either at the last row ($$$x = n$$$) or the last column ($$$y = m$$$).
  • Kingsnow can only move from a city $$$(x_i, y_i)$$$ to either $$$(x_i+1, y_i)$$$ or $$$(x_i, y_i+1)$$$. Thus, for each step $$$i$$$ in the route (except for the last step in the route), $$$(x_{i+1}, y_{i+1})$$$ must be chosen such that it is either directly below or directly to the right of $$$(x_i, y_i)$$$.

Once on the route, Kingsnow will purchase an item in the first city of the route $$$(1, 1)$$$. He will then arbitrarily select another city on the route to sell this item. Additionally, he will pay travel expenses for every city visited between the city where he starts the journey and the city where he sells the item.

That is to say, for any given route $$$(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)$$$, Kingsnow will arbitrarily select an integer $$$t$$$ from the interval $$$[2, k]$$$. The profit he makes from selling the item in city $$$(x_t, y_t)$$$ will be calculated as: $$$ \text{Profit} = a[x_t][y_t] - a[1][1] - \sum_{i=1}^t b[x_i][y_i] $$$

Kingsnow seeks a route such that no matter which city along the route he chooses to sell his item, he will always make a nonnegative profit.

Input

The first line contains two integers $$$n$$$ and $$$m(1\leq n,m\leq 1000)$$$— the number of lines and rows. Ensure that $$$n$$$ and $$$m$$$ do not equal $$$1$$$ at the same time.

For the next $$$n$$$ lines, each line contains $$$m$$$ integers in range $$$[1,10^9]$$$ denoting the price of the item in each city. The $$$y$$$-th integer in the $$$x$$$-th line is $$$a[x][y]$$$.

For the next $$$n$$$ lines, each line contains $$$m$$$ integers in range $$$[1,10^9]$$$ denoting the travel expense in each city. The $$$y$$$-th integer in the $$$x$$$-th line is $$$b[x][y]$$$.

Output

If there is at least one route that meets the requirements output "YES", otherwise output "NO".

Examples
Input
4 4
1 3 4 2
1 0 5 3
5 2 6 1
3 2 7 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Output
YES
Input
4 4
1 5 5 4
5 5 5 4
5 5 5 4
4 4 4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Output
NO