Stickers

Sanggeun's younger sister Sangnyang bought $2n$ stickers at a stationery store. They come stuck together in a grid of 2 rows and $n$ columns, and she wants to decorate her desk with them.

The stickers are made badly. When one is peeled off, every sticker that shares an edge with it tears and can no longer be used, so the stickers above, below, to the left, and to the right of the peeled one are lost.

Since she cannot use all of them, Sangnyang scores each sticker and peels off the set with the largest total score. Write a program that finds the maximum total score of a set chosen from the $2n$ stickers in which no two chosen stickers share an edge.

When the two highest scores sit on stickers that share an edge, those two cannot both be peeled off. The best set then has to use lower-scoring stickers that do not touch each other.

The first line contains the number of test cases $T$. The first line of each test case contains $n$ ($1 \le n \le 100000$). The next two lines each contain $n$ integers, where each integer is the score of the sticker at that position. Two consecutive integers are separated by a single space. Every score is an integer between $0$ and $100$, inclusive.

For each test case, print on its own line the maximum total score of a set of stickers in which no two share an edge.