E. Нижний уровень
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

На текущем уровне герой попал в систему из $$$n$$$ пещер, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ коридоров между ними. Каждый коридор соединяет две различные пещеры. Любые две пещеры соединены не более чем одним коридором. Из любой пещеры можно попасть в любую другую, двигаясь по коридорам.

Герой начинает уровень в пещере $$$1$$$, а в каждой из оставшихся пещер находится монстр.

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

По любому коридору герой может перемещаться в обоих направлениях. Однако герой не может использовать один и тот же коридор два раза подряд. Формально, если герой перешёл по коридору из пещеры $$$i$$$ в пещеру $$$j$$$, он не может сразу же направиться обратно в пещеру $$$i$$$, но может направиться в любую другую пещеру, соединённую коридором с пещерой $$$j$$$.

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

Чтобы пройти уровень, герою нужно победить монстров во всех пещерах. Когда герой впервые зайдёт в пещеру, ему придётся драться с монстром в ней. Герой может победить монстра в пещере $$$i$$$ только в том случае, если сила героя строго больше $$$a_i$$$. В случае победы над монстром сила героя увеличится на $$$b_i$$$. Если герой не может победить монстра, с которым он дерётся, игра заканчивается и игрок проигрывает.

После того, как герой победит монстра в пещере $$$i$$$, все последующие визиты в пещеру $$$i$$$ не будут иметь последствий — монстра в этой пещере уже не будет, но и сила героя не будет изменяться.

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

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

Во входных данных находятся несколько наборов входных данных. В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 1000$$$; $$$n \le m \le min(\frac{n(n-1)}{2}, 2000)$$$) — число пещер и коридоров.

Вторая строка содержит $$$n-1$$$ целых чисел $$$a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — значения, с которыми сравнивается сила героя при битве с монстрами в пещерах $$$2, 3, \ldots, n$$$.

Третья строка содержит $$$n-1$$$ целых чисел $$$b_2, b_3, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — прибавки к силе героя за победу над монстрами в пещерах $$$2, 3, \ldots, n$$$.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — номера пещер, соединённых коридором.

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$, а сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

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

Пример
Входные данные
3
4 4
11 22 13
8 7 5
1 2
2 3
3 4
4 1
4 4
11 22 13
5 7 8
1 2
2 3
3 4
4 1
5 7
10 40 20 30
7 2 10 5
1 2
1 5
2 3
2 4
2 5
3 4
4 5
Выходные данные
15
15
19
Примечание

В первом наборе входных данных герой может пройти уровень, начав с силы $$$15$$$, следующим образом:

  • перейти из пещеры $$$1$$$ в пещеру $$$2$$$: так как $$$15 > 11$$$, герой побеждает монстра, сила героя увеличивается до $$$15 + 8 = 23$$$;
  • перейти из пещеры $$$2$$$ в пещеру $$$3$$$: так как $$$23 > 22$$$, герой побеждает монстра, сила героя увеличивается до $$$23 + 7 = 30$$$;
  • перейти из пещеры $$$3$$$ в пещеру $$$4$$$: так как $$$30 > 13$$$, герой побеждает монстра, сила героя увеличивается до $$$30 + 5 = 35$$$.

Во втором наборе входных данных ситуация аналогична, но прибавки к силе героя в пещерах $$$2$$$ и $$$4$$$ поменялись местами. Герой может использовать другой маршрут, $$$1 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$, и пройти уровень с начальной силой $$$15$$$.

В третьем наборе входных данных герой может пройти уровень, начав с силы $$$19$$$, следующим образом:

  • перейти из пещеры $$$1$$$ в пещеру $$$2$$$: так как $$$19 > 10$$$, герой побеждает монстра, сила героя увеличивается до $$$19 + 7 = 26$$$;
  • перейти из пещеры $$$2$$$ в пещеру $$$4$$$: так как $$$26 > 20$$$, герой побеждает монстра, сила героя увеличивается до $$$26 + 10 = 36$$$;
  • перейти из пещеры $$$4$$$ в пещеру $$$5$$$: так как $$$36 > 30$$$, герой побеждает монстра, сила героя увеличивается до $$$36 + 5 = 41$$$;
  • перейти из пещеры $$$5$$$ в пещеру $$$2$$$: в этой пещере монстра уже нет, поэтому ничего не происходит;
  • перейти из пещеры $$$2$$$ в пещеру $$$3$$$: так как $$$41 > 40$$$, герой побеждает монстра, сила героя увеличивается до $$$41 + 2 = 43$$$.