Another Brick in the Wall

벽돌 더미를 순서대로 사용해 너비 w인 층을 h개 쌓을 때, 남은 벽돌이 부족하지 않고 모든 층을 정확히 채울 수 있는지 판단한다.

쉬움3시뮬레이션구현배열그리디면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

예전에 라르스라고 불리던 건설 노동자는 높이가 11이고 길이는 제각각인 벽돌을 잔뜩 쌓아 두었다. 라르스는 이 벽돌로 너비 ww, 높이 hh인 벽을 쌓으려고 한다. 부분집합 합 문제가 NP-난해라는 사실을 알기 때문에 라르스는 벽돌 배치를 최적화하지 않는다. 그냥 더미에 놓인 순서대로 벽돌을 집어서 쌓고, 잘 맞기를 바랄 뿐이다.

라르스는 첫 번째 층을 왼쪽에서 오른쪽으로 채운다. 그 층이 꽉 차면 두 번째 층으로 올라가 같은 방식으로 채우고, 그다음 층도 마찬가지로 채운다. 벽돌은 돌리지 않고 눕힌 채로만 놓으므로 벽돌 하나가 두 층에 걸치는 일은 없다. 집어 든 벽돌이 지금 층에 남은 자리보다 길어서 놓을 수 없으면, 라르스는 그 층을 끝내지 못한 채 짜증을 내고 떠난다. 벽을 다 쌓은 뒤에 벽돌이 남는 것은 상관없다.

어제 라르스는 마지막 층에 이르러서야 벽을 완성할 수 없다는 사실을 깨닫고, 몹시 짜증이 나서 벽을 허물어 버렸다. 오늘 라르스가 들고 온 벽돌 더미로 벽을 완성할 수 있는지 알려주자.

입력

첫째 줄에 세 정수 hh, ww, nn (1h1001 \le h \le 100, 1w1001 \le w \le 100, 1n100001 \le n \le 10000)이 주어진다. 각각 벽의 높이, 벽의 너비, 벽돌의 개수이다.

둘째 줄에 벽돌의 길이를 나타내는 정수 nnxix_i (1xi101 \le x_i \le 10)가 더미에 쌓인 순서대로 주어진다.

출력

라르스가 벽을 완성하면 YES를, 그렇지 않으면 NO를 출력한다.