Искусство кройки...
Задачу добавил: alef
Успешно сдано решений: 0
Время на тест - до 60 с
Наконец, друзья Елисея, ведомые человечком, оказались в огромной светлой зале. Зала была пуста, лишь вдоль стен стояли длинные деревянные скамьи. Человечек вышел на середину залы, поклонился и произнес:
- Великий маг, твои гости здесь, они ждут твоего задания!
Из дверей на другом конце залы вышли два человека, одетые в темно-синие плащи. Они несли скатанную в рулон, как поначалу показалось друзьям Елисея, ткань. Положив ее перед человечком, они что-то негромко сказали ему и тут же удалились.
- Идите сюда, великий маг сообщил свое задание! - позвал друзей человечек.
Как оказалось, в рулон была свернута старая скатерть, которой много лет подряд накрывали стол во время торжественных обедов у Ормуса. Прямоугольная скатерть была сшита из одинаковых по размеру квадратов (ради простоты будем полагать, что длина стороны квадрата равна единице), изготовленных из тканей разных цветов. Человечек чуть развернул рулон:
- Видите, некоторые квадраты безнадежно испорчены, потому что вот об этот, например, кто-то погасил факел, а здесь, наверное, хотели отрезать кусочек лепешки, но, надо думать, и на столе осталась отметина... Великий маг сначала хотел заменить испорченные квадраты, но так получилось, что теперь у нас есть новая скатерть, и поэтому он решил изготовить из этой салфетки. Будем класть эти салфетки на новую скатерть, и, быть может, она дольше будет выглядеть как новая...
Задание Ормуса, которое получили друзья, состояло в следующем. Прямоугольная скатерть длиной N и шириной M должна быть разрезана на салфетки длиной P и шириной Q таким образом, чтобы салфетки состояли только из неиспорченных квадратов. Разумеется, Ормус хочет, чтобы обрезков (т.е. неиспорченных квадратов, которые не войдут в состав ни одной салфетки) было как можно меньше. Ваша задача - помочь друзьям Елисея выполнить задание Ормуса.
Формат входного файла input.txt
Первая строка - целое число K (1 <= K <= 5) - количество блоков входных данных
Затем следует K блоков данных.
Каждый блок входных данных содержит в себе описание скатерти.
В первой строке описания пять целых чисел через пробел - N (1 <= N <= 100), M (1 <= M <= 10), P (1 <= P <= Q), Q (1 <= Q <= 5) и B (1 <= B <= M*N); B - количество испорченных квадратов
Каждая из следующих B строк описания содержит пару целых чисел X и Y (1 <= X <= N, 1 <= Y <= M) - координаты очередного испорченного квадрата (левый верхний квадрат имеет координаты X=1, Y=1, правый нижний - X=N, Y=M).
Формат выходного файла output.txt
В каждой из K строк выходного файла содержится по одному целому числу - количеству салфеток, которые можно получить из описанной скатерти.
Пример входного файла
2
6 6 2 3 5
1 4
4 6
2 2
3 6
6 4
6 5 2 3 4
3 3
6 1
6 2
6 4
Пример выходного файла
3
4