Оксана та Яна святкують день Святого Валентина. Для підготовки до свята вони склали список із ~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