25712번 - 인경강

평생을 시골에서 보낸 시은이는 첫 서울 여행에서 한강을 보고 크게 감동받았다. 그 감동을 INPC 참가자들에게도 전하기 위해, 대회가 진행되는 동안 인하대학교에 한강처럼 생긴 인경강을 만들기로 했다.

인경강을 만들 수 있는 예

인경강을 만들 수 없는 예

인하대학교의 부지는 직사각형으로, N행 M열의 정사각형 칸들로 구분할 수 있다. 1행이 가장 위, 1열이 가장 왼쪽이다. 각 칸을 땅 또는 물로 구분할 때, 다음 조건을 모두 만족하면 인경강을 만들 수 있다. 특히 마지막 조건에서 왼쪽으로 이동할 수 없음에 유의하자.

• 1번 열에 물이 한 칸 이상 있다.
• M번 열에 물이 한 칸 이상 있다.
• 어떤(적어도 하나) 1번 열의 물에서 출발하면 위 · 아래 · 오른쪽으로 인접한 물로 0번 이상 이동해 M번 열의 물에 도달할 수 있다.

입력으로 1열부터 M열까지 M개의 열 정보가 주어진다. 열 정보는 각 열에 물이 어떻게 분포하는지 나타내는 길이가 짝수인 수열이다. 수열은 빈 수열에서 시작해 다음 과정을 순서대로 시행해 만들어지며, 열에 물이 하나도 없는 경우는 주어지지 않는다.

1. 수열이 비어있다면 가장 위에 있는 물의 행 번호를, 그렇지 않다면 행 번호가 수열의 마지막 수보다 큰 물 중 가장 위에 있는 것의 행 번호를 수열의 맨 뒤에 추가한다.
2. 행 번호가 수열의 마지막 수인 물에서 출발해, 아래로 인접한 물로 0번 이상 이동해 도달할 수 있는 물 중 행 번호가 가장 큰 것을 수열의 맨 뒤에 추가한다.
3. 행 번호가 수열의 마지막 수보다 큰 물이 있다면 1번 과정으로 돌아가고, 없다면 열 정보가 완성되었으므로 마친다.

인하대학교 부지의 크기와 M개의 열 정보가 주어지면, 인경강을 만들 수 있는지 판별해보자.

첫째 줄에 인하대학교 부지의 크기 N과 M이 공백을 구분으로 주어진다.

둘째 줄에 1열의 열 정보의 길이, 2열의 열 정보의 길이, …, M열의 열 정보의 길이를 나타내는 M개의 정수가 공백을 구분으로 주어진다.

다음 M개의 줄에 걸쳐, M개의 열 정보가 열의 오름차순으로 주어진다. 각 열 정보의 수들은 공백으로 구분해 주어진다.

인경강을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

• 1 ≤ N ≤ 1,000,000,000
• 1 ≤ M ≤ 100,000
• 2 ≤ 열 정보의 길이 ≤ 20