Under construction

Still being built. Things may change

City and Bitcoin

Interview

Time limit1sMemory limit512 MB

Summary
Determines whether a path exists from the top-left to the bottom-right of a grid using only right and down moves through open cells.
Level

Easy2 of 10

Topics
Matrix, Dynamic programming
Solved
No attempts yet

Problem

Bitcoin's price rose by a full million won from the previous day one morning, and Woojin decides to go to the exchange to sell some. The price keeps falling, so he must reach the exchange as quickly as possible.

The city is a grid with NN columns and MM rows. Some cells are empty ground or roads that Woojin can pass through, while other cells contain buildings he cannot enter. Woojin starts at the top-left corner, and the exchange is at the bottom-right corner.

Because he must hurry, he has to reach the exchange by moving only east (right) or south (down). Write a program that determines whether Woojin can reach the exchange. His current position may already be the exchange.

Input

The first line contains NN and MM (1≤N,M≤3001 \le N, M \le 300), the width and height of the city.

The next MM lines each contain NN integers separated by spaces. A 1 marks a cell Woojin can enter, and a 0 marks a cell he cannot enter.

The top-left and bottom-right cells are both 1.

Output

Print Yes if Woojin can reach the exchange. Otherwise, print No.

Examples1

  1. Example 1

    Input
    5 4
1 1 1 1 1
0 1 0 0 1
1 0 0 0 1
0 0 0 1 1
    Expected output
    Yes