Мальчик Петя очень любит игровые автоматы. Сегодня он решил поиграть на одном из них.
Автомат имеет три барабана по $$$n$$$ ячеек, в каждой из которых записано по одному целому числу. На первом барабане записаны числа $$$a_1, a_2, \ldots, a_n$$$, на втором — $$$b_1, b_2, \ldots, b_n$$$; на третьем — $$$c_1, c_2, \ldots, c_n$$$. В любой момент времени на каждом из барабанов видно только одно число из записанных. В начальный момент времени на каждом из барабанов видны первые элементы, то есть значения $$$a_1$$$, $$$b_1$$$ и $$$c_1$$$.
Одна игра с таким автоматом стоит $$$cost$$$ монет. После оплаты барабаны поворачиваются циклически (после ячейки с номером $$$n$$$ снова идет первая ячейка): первый на $$$x$$$ ячеек вправо, второй на $$$y$$$, третий на $$$z$$$.
После поворота барабанов выполняется проверка выигрыша. Если на всех барабанах видно одно и то же число, то игрок получает выигрыш, который равен значению этого числа, иначе не получает ничего.
Петя может прекратить игру в любой момент, в том числе не начав играть вовсе, но он будет играть не больше $$$q$$$ раз. Петя знает все числа на барабанах, величины поворотов, но не знает, как посчитать максимальную прибыль. Прибыль — это разница между суммарным выигрышем и стоимостью совершённых игр.
Помогите Пете определить максимальную прибыль, которую он может получить.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
В первой строке каждого набора входных данных содержится три целых числа $$$n$$$, $$$cost$$$ и $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le cost \le 10^9$$$, $$$1 \le q \le 10^9$$$) — размер барабанов, стоимость одной игры и максимальное число игр соответственно.
Во второй строке каждого набора входных данных содержится три целых числа $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \le x,y,z \le 10^9$$$) — величины поворотов барабанов.
В третьей строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i \le 10^9$$$) — числа в ячейках первого барабана. Перед началом первой игры на барабане видно число $$$a_1$$$, остальные числа перечислены в порядке поворота барабана.
В четвёртой строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i \le 10^9$$$) — числа в ячейках второго барабана. Перед началом первой игры на барабане видно число $$$b_1$$$, остальные числа перечислены в порядке поворота барабана.
В пятой строке входных данных содержится $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1\le c_i \le 10^9$$$) — числа в ячейках третьего барабана. Перед началом первой игры на барабане видно число $$$c_1$$$, остальные числа перечислены в порядке поворота барабана.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальную возможную прибыль Пети.
410 1 35 3 414 11 11 11 10 13 10 14 12 1410 12 10 13 10 12 14 11 13 1212 11 12 11 10 14 11 11 14 1310 0 910 7 42 3 3 3 4 3 1 1 5 22 5 1 2 2 5 1 5 3 11 3 1 1 5 2 2 1 1 53 1 1001 1 13 3 37 7 78 8 81 1 31 1 1222
12203
В первом наборе входных данных максимальная прибыль достигается после второй игры. После первой игры будут видны числа $$$a_6$$$, $$$b_4$$$ и $$$c_5$$$. Но они не равны между собой, поэтому выигрыша не будет. После второй игры будут видны числа $$$a_1$$$, $$$b_7$$$ и $$$c_9$$$. Все эти числа равны между собой, поэтому выигрыш будет равен $$$14$$$. Суммарные затраты на две игры будут равны $$$1 \cdot 2 = 2$$$.
Во втором наборе входных данных максимальная прибыль достигается после последней, $$$9$$$-й игры. Закончив игру раньше, Петя остался бы вообще без выигрыша.
В третьем наборе входных данных Пете выгодно даже не начинать игру. Поскольку на барабанах вообще нет совпадающих чисел, выигрыша он никогда не получит.