В некоторой компьютерной игре игрок управляет героем, который характеризуется одним целочисленным параметром — силой.
На текущем уровне герой попал в систему из $$$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$$$, следующим образом:
Во втором наборе входных данных ситуация аналогична, но прибавки к силе героя в пещерах $$$2$$$ и $$$4$$$ поменялись местами. Герой может использовать другой маршрут, $$$1 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$, и пройти уровень с начальной силой $$$15$$$.
В третьем наборе входных данных герой может пройти уровень, начав с силы $$$19$$$, следующим образом:
Название |
---|