카펫

시간 제한1초메모리 제한256 MB

요약

주어진 카페트를 90도 돌려 W by H 방을 겹침 없이 빈틈없이 덮을 수 있는지 판정합니다.

난이도: 보통10점 중 6점
유형: 백트래킹, 재귀
정답자: 아직 제출이 없습니다

문제

컴퓨터공학과 토빙 라일스 교수는 연구실 바닥 타일을 아껴서, 조심성 없는 학생이 타일을 망가뜨리지 않도록 보호하려고 한다. 그래서 마트에서 값싼 작은 직사각형 카펫을 사다가 다음 네 조건을 모두 지키며 바닥을 덮으려 한다.

바닥 전체를 덮는다.
카펫끼리 겹치지 않는다.
카펫은 90도 돌려서 깔아도 된다. 즉 $w \times h$ 카펫을 $h \times w$ 카펫으로도 쓸 수 있다.
카펫을 잘라서 나누지 않는다.

카펫은 항상 변이 벽과 평행하도록 깔고, 마트에 있는 카펫을 전부 살 필요는 없다. 교수가 계획대로 바닥을 덮을 수 있는지 판정하라.

입력

첫째 줄에 방의 가로 길이 $W$ 와 세로 길이 $H$ 가 주어진다 ( $1 \le W, H \le 100$ ).

둘째 줄에 마트가 취급하는 카펫 색의 수 $c$ 가 주어진다 ( $1 \le c \le 7$ ).

이어지는 $c$ 개 줄에는 각각 세 정수 $a_i$ , $w_i$ , $h_i$ 가 주어진다. 마트에 크기가 $w_i \times h_i$ 인 색 $i$ 카펫이 $a_i$ 장 있다는 뜻이다 ( $1 \le a_i \le 7$ ; $1 \le w_i \le 100$ ; $1 \le h_i \le 100$ ).

마트에 있는 카펫은 모두 합쳐 7장을 넘지 않는다. 즉 $\sum_i a_i \le 7$ 이다.

출력

조건을 지키며 방 바닥을 덮을 수 있으면 yes를, 덮을 수 없으면 no를 출력한다.

예제2

예제 1
입력
```
2 4
2
3 1 3
2 2 1
```
예상 출력
```
yes
```
예제 2
입력
```
100 100
3
4 42 42
1 100 16
1 32 42
```
예상 출력
```
no
```