e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

2015 German Collegiate Programming Contest (GCPC)

Ковры

Профессор компьютерных наук Товинг Лайлс так любит плитку на полу в своем офисе, что хочет защитить ее от повреждений нерадивыми учениками. Поэтому он хотел бы купить в супермаркете дешевые небольшие прямоугольные коврики и покрыть пол таким образом, чтобы:

  1. Весь пол был покрыт.

  2. Коврики не должны пересекаться.

  3. Коврики можно вращать произвольным образом.

  4. Коврики нельзя рвать на куски.

Но, проверяя запасы супермаркета, он начинает задаваться вопросом, сможет ли он вообще осуществить свой план. Вы можете ему помочь?

Входные данные

Первая строка содержит два целых числа w и h (1w, h100) - размеры комнаты. Вторая строка содержит целое число c (1c7) - количество ковров разных цветов, имеющихся в наличии в супермаркете.

Каждая из следующих c строк содержит три целых числа ai, wi и hi, означающих что супермаркет содержит ai ковриков размера wi, hi и цвета i (1ai7, 1wi100, 1hi100).

Супермаркет содержит не более 7 ковров, то есть сумма всех ai7.

Выходные данные

Для заданных размеров помещения и наличия ковров в супермаркете выведите "yes", если можно застелить комнату коврами как указано выше и "no" иначе.

Лимит времени 2 секунды
Лимит использования памяти 128 MiB
Входные данные #1
2 4
2
3 1 3
2 2 1
Выходные данные #1
yes
Входные данные #2
100 100
3
4 42 42
1 100 16
1 32 42
Выходные данные #2
no
Источник 2015 German Collegiate Programming Contest (GCPC), June 20, Problem D