Another Brick in the Wall
면접 대비시간 제한2초메모리 제한512 MB
벽돌 더미를 순서대로 사용해 너비 w인 층을 h개 쌓을 때, 남은 벽돌이 부족하지 않고 모든 층을 정확히 채울 수 있는지 판단한다.
문제
예전에 라르스라고 불리던 건설 노동자는 높이가 이고 길이는 제각각인 벽돌을 잔뜩 쌓아 두었다. 라르스는 이 벽돌로 너비 , 높이 인 벽을 쌓으려고 한다. 부분집합 합 문제가 NP-난해라는 사실을 알기 때문에 라르스는 벽돌 배치를 최적화하지 않는다. 그냥 더미에 놓인 순서대로 벽돌을 집어서 쌓고, 잘 맞기를 바랄 뿐이다.
라르스는 첫 번째 층을 왼쪽에서 오른쪽으로 채운다. 그 층이 꽉 차면 두 번째 층으로 올라가 같은 방식으로 채우고, 그다음 층도 마찬가지로 채운다. 벽돌은 돌리지 않고 눕힌 채로만 놓으므로 벽돌 하나가 두 층에 걸치는 일은 없다. 집어 든 벽돌이 지금 층에 남은 자리보다 길어서 놓을 수 없으면, 라르스는 그 층을 끝내지 못한 채 짜증을 내고 떠난다. 벽을 다 쌓은 뒤에 벽돌이 남는 것은 상관없다.
어제 라르스는 마지막 층에 이르러서야 벽을 완성할 수 없다는 사실을 깨닫고, 몹시 짜증이 나서 벽을 허물어 버렸다. 오늘 라르스가 들고 온 벽돌 더미로 벽을 완성할 수 있는지 알려주자.
입력
첫째 줄에 세 정수 , , (, , )이 주어진다. 각각 벽의 높이, 벽의 너비, 벽돌의 개수이다.
둘째 줄에 벽돌의 길이를 나타내는 정수 개 ()가 더미에 쌓인 순서대로 주어진다.
출력
라르스가 벽을 완성하면 YES를, 그렇지 않으면 NO를 출력한다.