Problem1201--取数游戏

1201: 取数游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 115  Solved: 82
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI和POPO在玩一个取数游戏。

给定两个长度为N的整数数组A1, A2, ... AN和B1, B2, ... BN。他们轮流选择一个非空数组,取出该数组的第一个整数,加到自己的分数中。直到2N个整数都被取走为止,分数高的选手获胜。

现在PIPI是先手,他知道POPO一定会采取最优策略。PIPI想知道自己最多能得多少分。

Input

第一行一个整数N。  

第二行包含N个整数A1, A2, ... AN。  

第三行包含N个整数B1, B2, ... BN。  

1 <= N <= 1000  

1 <= Ai, Bi <= 10000000 

Output

一个整数代表答案

Sample Input

3
1 100 10000
1000 10000 10

Sample Output

10101

Source/Category