1741. Шляпа

Фокусник Аркадий Великолепный разочаровался в доходности извлечения из цилиндра кроликов и голубей и решил заняться контрабандой драгоценностей. Его шляпа-цилиндр, высотой `H` и радиусом основания `R`, поможет ему в этом, ибо ни один таможенник не сможет обнаружить там ничего, кроме кучки заячьего помета. Перед Аркадием, однако, встал другой вопрос: что и куда везти? Разные драгоценности пользуются разной популярностью в разных городах; кроме того, драгоценности различаются между собой по размеру упаковки. Ценности хранятся в кубических контейнерах, которые размещаются в цилиндре так, что их дно параллельно дну цилиндра. Контейнеры могут помещаться друг на друга, образуя слои, причем в одном слое могут находиться только контейнеры с одинаковой длиной ребра. Из-за чисто технических ограничений более пяти контейнеров в один слой поместить нельзя. Контейнеры не должны выступать за границы цилиндра.

Аркадий выяснил, какой длины ребро у контейнеров всех типов драгоценностей, и по какой цене можно продать те или иные драгоценности в тех или иных городах. Для начала фокусник решил совершить поездку в один город, взяв с собой драгоценности одного типа. Помогите ему рассчитать прибыль от сделки при такой упаковке цилиндра контейнерами, когда помещается их максимально возможное количество.

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит четыре числа, разделенных пробелами: `N` – количество типов драгоценностей (`1\ ≤\ N\ ≤\ 10`), `M` – количество городов (`1\ ≤\ M\ ≤\ 10`), действительные числа `R` (`1.0\ ≤\ R\ ≤\ 100.0`) и `H` (`1.0\ ≤\ H\ ≤\ 100.0`).

На следующей строке расположены `N` действительных чисел `a_1\ a_2\ …\ a_N` – длина ребер контейнеров каждого типа драгоценностей, `0.5\ ≤\ a_i\ ≤\ 100.0`. Далее во входном файле `M` строк – по одной для каждого города. Каждая из строк содержит `N` целых чисел `Q_{ij}` – стоимость драгоценностей каждого типа в текущем городе (`0\ ≤\ Q_{ij}\ ≤\ 1000`).

Для каждого теста в выходной файл выводится максимальная прибыль, которую фокусник может извлечь в текущей ситуации.

2
2 2 1 2
1 2
10 20
30 40
3 3 1 2
1 0.5 1
10 10 10
20 20 20
30 30 30

60
600