|
Шляпа
(Время: 1 сек. Память: 16 Мб Сложность: 59%)
Фокусник Аркадий Великолепный разочаровался в доходности извлечения из цилиндра кроликов и голубей и решил заняться контрабандой драгоценностей. Его шляпа-цилиндр, высотой H и радиусом основания R, поможет ему в этом, ибо ни один таможенник не сможет обнаружить там ничего, кроме кучки заячьего помета. Перед Аркадием, однако, встал другой вопрос: что и куда везти? Разные драгоценности пользуются разной популярностью в разных городах; кроме того, драгоценности различаются между собой по размеру упаковки. Ценности хранятся в кубических контейнерах, которые размещаются в цилиндре так, что их дно параллельно дну цилиндра. Контейнеры могут помещаться друг на друга, образуя слои, причем в одном слое могут находиться только контейнеры с одинаковой длиной ребра. Из-за чисто технических ограничений более пяти контейнеров в один слой поместить нельзя. Контейнеры не должны выступать за границы цилиндра.
Аркадий выяснил, какой длины ребро у контейнеров всех типов драгоценностей, и по какой цене можно продать те или иные драгоценности в тех или иных городах. Для начала фокусник решил совершить поездку в один город, взяв с собой драгоценности одного типа. Помогите ему рассчитать прибыль от сделки при такой упаковке цилиндра контейнерами, когда помещается их максимально возможное количество.
Входные данные
Первая строка входного файла INPUT.TXT содержит четыре числа, разделенных пробелами: N – количество типов драгоценностей (1 ≤ N ≤ 10), M – количество городов (1 ≤ M ≤ 10), действительные числа R (1.0 ≤ R ≤ 100.0) и H (1.0 ≤ H ≤ 100.0).
Во второй строке расположены N действительных чисел a1, a2, …, aN – длина ребер контейнеров каждого типа драгоценностей, 0.5 ≤ ai ≤ 100.0. Далее во входном файле M строк – по одной для каждого города. Каждая из строк содержит N целых чисел Qij – стоимость драгоценностей каждого типа в текущем городе (0 ≤ Qij ≤ 1000).
Все вещественные числа во входных данных имеют не более 6 значащих разрядов.
Выходные данные
В выходной файл OUTPUT.TXT выведите максимальную прибыль, которую фокусник может извлечь в текущей ситуации.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 2 1 2
1 2
10 20
30 40 | 60 |
2 | 3 3 1 2
1 0.5 1
10 10 10
20 20 20
30 30 30 | 600 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |