Problem E
A Game in the Park
It’s a beautiful Saturday afternoon. As you take stroll through the park, you stumble upon an old man who asks you to come over. For some reason, you oblige, and ask him what he’s up to. He makes a bet with you, proposing that if he can make a higher score in a game he will explain shortly, he wins. But, if you can make the highest score possible, you win. The game is as follows:
The old man shows you a $4 \times n$ grid of integers like the one below and gives you $2n$ stones. He tells you to place as many (or as little) of the stones as you want on the grid such that no two stones are adjacent (horizontally or vertically) and try to get the highest possible sum of the numbers under the stones.
It’s a very simple game to play, but a hard one to master. Can you beat your new friend?
Input
The input consists of five lines. The first line is an integer, $n$ ($2 \le n \le 100\, 000$), which represents the length of the grid. The next four lines consists of $n$ integers each, $x_1$-$x_ n$ ($-1\, 000 \le x_ i \le 1\, 000$), and represent the numbers in the grid.
Output
Your job is to output the maximum possible score you can achieve for the given board.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 1 4 5 -5 5 9 0 12 0 1 2 |
30 |
