Ingyeonggang

Time limit2sMemory limit1024 MB

Summary

Given each column's water cells in a compressed form, decide whether water can flow from column 1 to column M moving up, down, or right.

Level: Medium5 of 10
Topics: Intervals, Two pointers, Implementation
Solved: No attempts yet

Problem

Sieun spent her whole life in the countryside. On her first trip to Seoul, she was deeply moved by the Han River. To share that feeling with INPC participants, she decided to build a river like the Han at Inha University during the contest. This river is called Ingyeonggang.



Examples where Ingyeonggang can be built

Examples where Ingyeonggang cannot be built

The Inha University site is a rectangle divided into $N$ rows and $M$ columns of square cells. Row 1 is the top row and column 1 is the leftmost column. Each cell is either land or water. Ingyeonggang can be built if all of the following conditions hold. Note that the last condition does not allow moving left.

Column 1 has at least one water cell.
Column $M$ has at least one water cell.
Starting from some water cell in column 1 (at least one), you can move up, down, or right through adjacent water cells, zero or more times, to reach a water cell in column $M$ .

The input gives $M$ column descriptions, from column 1 to column $M$ . A column description is an even-length sequence that shows how water is distributed in that column. The sequence starts empty and is built by running the following steps in order. No column is given without water.

If the sequence is empty, append the row number of the topmost water cell. Otherwise, append the row number of the topmost water cell whose row number is greater than the last number of the sequence.
Starting from the water cell whose row number is the last number of the sequence, move down through adjacent water cells zero or more times. Among the water cells reached, append the one with the largest row number to the end of the sequence.
If there is a water cell with a row number greater than the last number of the sequence, go back to step 1. Otherwise, the column description is complete and the process ends.

Given the site size and the $M$ column descriptions, determine whether Ingyeonggang can be built.

Input

The first line contains $N$ and $M$ , separated by a space.

The second line contains $M$ integers, the lengths of the column descriptions for column 1, column 2, ..., column $M$ , separated by spaces.

The next $M$ lines give the $M$ column descriptions in ascending column order. The numbers in each description are separated by spaces.

Output

Print YES if Ingyeonggang can be built, otherwise print NO.

Constraints

$1 \le N \le 1{,}000{,}000{,}000$
$1 \le M \le 100{,}000$
$2 \le$ length of a column description $\le 20$

Examples5

Example 1

Input

8 10
2 4 2 2 2 2 4 4 4 2
4 4
2 2 4 5
5 5
4 5
3 4
3 6
2 4 6 6
2 2 4 6
2 2 5 5
4 7

Expected output

YES

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

Example 5

Input

2000 5
2 4 8 4 2
1 1999
1 1 1999 1999
1 1 134 135 1279 1947 1999 1999
2 2 2000 2000
2 2000

Expected output

NO