Снежная крепость (35 баллов)
Задачу добавил: alef
Успешно сдано решений: 14
После встречи нового года друзья вышли на улицу. Погода - замечательная, много снега. И кому-то пришла в голову идея построить снежную крепость. Для этого друзья принялись скатывать снег в шары, и чрезвычайно этим увлеклись. Получилось так, что во дворе (который ради простоты будем считать прямоугольником размером P x Q метров) оказалось М больших и тяжелых скатанных шаров, расположенных в разных местах. А для построения крепости достаточно K шаров. Поэтому нужно выбрать участок, на котором будет построена крепость, таким образом, чтобы он имел наименьшую площадь (тогда трудозатраты на перемещение шаров будем считать наименьшими).
Формат входного файла input.txt
Первая строка - два целых числа P и Q - размеры двора (1<=P,Q<=200)
Вторая строка - два целых числа M и K (1<=K<=M<=100) через пробел: количество существующих шаров и количество шаров, достаточное для построения крепости.
Следующие M строк - пары целых чисел Sx,Sy, обозначающие координаты каждого из M шаров (1<=Sx<=P, 1<=Sy<=Q).
Формат выходного файла output.txt
Целое число - минимально возможная площадь участка, на котором расположены K шаров
Пример входного файла
200 200
1 1
5 200
Пример выходного файла
1