F. Недовольство автомобилистов
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В одном королевстве имеется n городов и m двусторонних дорог. Каждая дорога соединяет пару городов, причём для каждой дороги известен уровень недовольства ею автомобилистами — величина wi.

Для каждой дороги известна величина ci — сколько надо потратить лямзиков, чтобы уменьшить уровень недовольства этой дорогой на единицу. Таким образом, чтобы уменьшить недовольство i-й дорогой на k, надо потратить k·ci лямзиков. При этом допустимо, чтобы недовольство стало нулевым или даже отрицательным.

В соответствии с приказом короля, необходимо выбрать n - 1 дорогу, сделав их главными дорогами. Должно выполняться важное условие: из любого города должно быть возможно проехать в любой другой по главным дорогам.

У министерства дорог есть бюджет S лямзиков на проведение реформы. Министерство планирует потратить этот бюджет на ремонт некоторых дорог (то есть уменьшить недовольство ими), а уже затем выбрать n - 1 главную дорогу.

Помогите потратить бюджет так, а затем и произвести выбор главных дорог, чтобы суммарное недовольство главными дорогами было как можно меньше. При этом величина недовольства некоторыми дорогами может стать отрицательной. Не обязательно тратить весь бюджет S полностью.

Гарантируется, что из любого города королевства можно добраться по дорогам в любой другой город королевства. Каждая дорога в королевстве — двусторонняя.

Входные данные

В первой строке входных данных находится два целых числа n и m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — количество городов и дорог в королевстве соответственно.

Во второй строке входных данных содержатся m целых чисел w1, w2, ..., wm (1 ≤ wi ≤ 109), где wi — недовольство автомобилистов i-й дорогой.

В третьей строке входных данных содержатся m целых чисел c1, c2, ..., cm (1 ≤ ci ≤ 109), где ci  — стоимость в лямзиках уменьшения недовольства i-й дорогой на единицу.

В следующих m строках находятся описания дорог. В i-ой из этих строк находится пара целых чисел ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — означающих, что i-я дорога соединяет города ai и bi. Так как все дороги двусторонние, то по i-й дороге можно переместиться как из ai в bi, так и наоборот. Допустимо, что пара городов соединена более чем одной дорогой.

В последней строке входных данных находится одно число S (0 ≤ S ≤ 109) — количество лямзиков, которые можно потратить на проведение реформы.

Выходные данные

В первой строке выведите K — минимально возможное суммарное недовольство главными дорогами.

В следующих n - 1 строках выведите по два целых числа x, vx — означающих, что дорога x является главной, и дорога x после реформы имеет уровень недовольства vx.

Считайте, что дороги пронумерованы от 1 до m в порядке их задания во входных данных. Номера рёбер можно выводить в произвольном порядке. Если решений несколько, выведите любое.

Примеры
Входные данные
6 9
1 3 1 1 3 1 2 2 2
4 1 4 2 2 5 3 1 6
1 2
1 3
2 3
2 4
2 5
3 5
3 6
4 5
5 6
7
Выходные данные
0
1 1
3 1
6 1
7 2
8 -5
Входные данные
3 3
9 5 1
7 7 2
2 1
3 1
3 2
2
Выходные данные
5
3 0
2 5