730. Greed and Meet

0

Easy

Two college friends Aniket and Bhanu decided to meet after 10 years at an arcade. They decided to play a game. In the game, there are N distinct number arranged from left to right. They play turn by turn and can choose either the leftmost number or rightmost number. Since both Aniket and Bhanu are greedy, so during their turn they will choose the highest number.
The number which they will choose will get added to their score. Find the final score of Aniket and Bhanu if Aniket moves first.

Input Format

The first line contains integer N.

The second line contains N space-separated numbers from left to right.

The second line contains N space-separated numbers from left to right.

Output Format

On a single line, print two integers : Aniket's score and Bhanu's score separated by a space.

Example

Input

4
4 1 2 10

Output

12 5

Constraints

1 ≤ N ≤ 1000.

Numbers are from 1 to 1000.

Numbers are from 1 to 1000.

Loading...

View Submissions

Console