Persuasion

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Java 1.5s
Python 1.5s
Memory limit: 128M

Author:
Problem type

You are trying to convince your friend to do your homework for you. Rather than bribing them like usual, you decide to persuade them using a new gadget you invented called the speech wheel.

The wheel is divided into N identical sectors, numbered from 1 to N in clockwise order. The ith sector has a value of ai, representing its effectiveness on your friend.

Initially, each sector is occupied by a circular pie, with the pie in the ith sector having a value of mi. At the end of a round, each pie moves to the next sector in clockwise order.

During each round, you will pick an unselected sector. If you pick sector i, and pie j is currently occupying it, your score for that round is aimj. Your total score is the sum of your scores for each round.

A higher score means a greater probability to persuade your friend. Please find the maximum total score you can achieve if you continue until every sector has been picked.

For this problem, Python users are recommended to use PyPy.

Input Specification

The first line contains the integer N (1N19).

The next line contains the space-separated integers a1,a2,,aN (|ai|104).

The final line contains the space-separated integers m1,m2,,mN (1mi104).

Output Specification

Output one line containing the maximum score you can achieve.

Sample Input

Copy
4
2 -1 1 -2
1 2 3 4

Sample Output

Copy
6

Explanation for Sample Output

One way to get a total score of 6 is the following:

Round 1: Pick sector 3 giving 13=3

Round 2: Pick sector 2 giving 11=1

Round 3: Pick sector 1 giving 23=6

Round 4: Pick sector 4 giving 21=2


Comments

There are no comments at the moment.