22117번 - Две башни 다국어

Компания Mail.World недавно переехала в новый офис, который имеет вид двух башен-небоскребов по 10⁹ этажей каждая. На некоторых этажах они соединены переходами, по которым можно перейти из одной башни в другую. Всего есть n переходов, они соединяют башни на этажах a₁, a₂, ..., a_n

Артем работает в башне b₁ на L₁-м этаже. Сегодня ему необходимо пообщаться со своим коллегой Дмитрием, который работает в башне b₂ на L₂-м этаже. Как ни странно, оказалось, что выбрать самый быстрый способ добраться от рабочего места Артема до рабочего места Дмитрия не так то просто.

В каждой из башен установлен один лифт. Лифт в башне 1 проезжает один этаж за время u₁ секунд, а лифт в башне 2 — за u₂ секунд. На переход между башнями по переходу Артем тратит t секунд.

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

В первом примере Артему необходимо просто проехать на лифте первой башни.

Во втором примере лифт во второй башне ходит существенно быстрее и Артему выгоднее перейти по переходу во вторую башню, проехать на лифте до 10 этажа, вернуться в первую башню и проехать еще 1 этаж на лифте в первой башне.

Первая строка содержит целое положительное число t — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Первая строка содержит n — число переходов между башнями (1 ≤ n ≤ 10⁵). Вторая строка содержит n различных целых чисел a₁, a₂, ..., a_n (1 ≤ a₁ < a₂ < ... < a_n ≤ 10⁹). Следующая строка содержит три целых положительных числа: u₁, u₂ и t (каждое из них лежит в диапазоне от 1 до 10⁹). Наконец, следующие две строки содержат по два числа: b₁, L₁ и b₂, L₂, соответственно (каждое из b₁ и b₂ равно 1 или 2, 1 ≤ L₁, L₂ ≤ 10⁹).

Суммарное число переходов во всех тестовых примерах во входных данных не превосходит 10⁶.

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