Побег
Автор задачи: Я
Первоисточник: Я
URL первоисточника: Я
Задачу добавил: Сашусик
Успешно сдано решений: 2
Зеки решили совершить побег из тюрьмы. Для этого им необходимо проделать дыру в решетке. В ряспоряжеинии зеков имеется один отстойный напильник. Решетка представляет из себя сетку из равных по размеру ячеек, состоящих из прутьев различной жесткости, спаянных в узловых точках:
0--0--0--0
| | | |
0--0--0--0
| | | |
0--0--0--0
| | | |
0--0--0--0
Чем жестче прутья, тем дольше они пилятся.
В решетке необходимо прорезать дыру требуемой формы и размера за минимальное время.
Необходимо подсчитать, сколько зеков может успеть вылезти через эту дыру, если известно, сколько времени требуется одному зеку на вылазку, а также известно время до следующего прихода проверки.
ВХОДНОЙ ФАЙЛ:
1-строка:целые числа 3<=N<=M<=100, N - размер образа прорези. M - размер решетки в ячейках
далее (M+1) строк жесткость горизонтальных прутьев: в каждой строке M целых чисел соответственно жесткость горизонтальных прутьев этого ряда слева направо.
далее M строк жесткость вертикальных прутьев: в каждой строке M+1 целых чисел - жесткость прутьев соответствующего ряда сверху вниз.
(все числа не превышают сотни по модулю. Жесткость означает время, необходимое для пропилки поответствующего прута)
далее N строк - описание прорези в формате "#" - прорезь, " " - целая ячейка.
последняя строка - целые числа X,T, где X - время вылезания одного зека, T - время до патруля.
ВЫХОДНОЙ ФАЙЛ:
Целое число - число зеков, которые выберутся на свободу.
Пример входого файла:
3 3
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
#
###
#
5 100
Пример выходого файла:
4