Оксана та Яна святкують день Святого Валентина. Для підготовки до свята вони склали список із \(N\) завдань, які їм треба виконати.

Для виконання \(і\)-го завдання Оксані треба \(X_i\) секунд, а Яні — \(Y_i\) секунд. Для того щоб мінімізувати час на підготовку до свята, вони вирішили виконати завдання почергово. Тобто, якщо Оксана виконує перше завдання, то після цього Яна виконує друге, потім Оксана третє і так далі. Порядок зміниться, якщо перше завдання буде виконувати Яна.

Допоможіть Оксані та Яні знайти мінімально можливий час, необхідний для виконання всіх \(N\) завдань почергово.

Формат вхідних даних

Перший рядок вхідного потоку містить \(Т\) \((1 ≤ T ≤ 10)\) — кількість тестів. Далі йде опис тестів у наступному форматі:

Перший рядок кожного тесту містить єдине число \(N\) \((1 ≤ N ≤ 2 ·10^4) \) — кількість завдань.

Другий рядок тесту містить \(N \) розділених пропуском цілих чисел, де \(і\)-те число є кількістю секунд, необхідних Оксані для виконання \(і\)-го завдання.

Третій рядок кожного тесту містить \(N\) розділених пропуском цілих чисел, де \(і\)-те число є кількістю секунд, необхідних Яні для виконання \(і\)-го завдання.

\((1 ≤ X_i, Y_i ≤ 10^5)\)

Формат вихідних даних

Для кожного тесту вивести в окремому рядку єдине ціле число — мінімальний час, необхідних для виконання всіх \(N\) завдань

Приклад вхідних даних

1
3
2 1 2
3 2 1

Приклад вихідних даних

5