В некоторой компьютерной игре игрок управляет героем, который характеризуется одним целочисленным параметром — силой.
На текущем уровне герой попал в систему из \(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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную силу героя, необходимую для того, чтобы иметь возможность победить всех монстров и пройти уровень.
Примечание
В первом наборе входных данных герой может пройти уровень, начав с силы \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|