Description
Solutions
Grandmaster's Choice

Sakaar is a trash planet created by the Grandmaster in the Tayo star system, and is surrounded by numerous wormholes that deposit space waste.

On the planet Sakaar, the Grandmaster hosts an annual gladiatorial event where each warrior is identified by a unique Warrior Number (w) and a unique Power Level (p). Despite his love for chaos and thrilling battles, the Grandmaster sometimes enjoys a bit of strategy and intrigue.

The total chaos score of the event is calculated as the sum of the scores from each fight as long as there are at least two warriors remaining in the arena.

In a single fight:

  • The Grandmaster selects two warriors from the arena, let's call them A and B.
  • Choose the Power Level (p[A]) of one warrior and the Warrior Number (w[B]) of the other. Multiply these numbers together and add the result to the total chaos score. Alternatively, you can choose p[B] * w[A].
  • One warrior (say A) returns to the arena, while the other warrior (say B) is thrown outside, or vice versa, meaning B returns and A is thrown outside.

In the final fight, both warriors leave the arena.

Sometimes, the Grandmaster enjoys a change of pace, focusing on minimizing the chaos score for a twist in the usual chaos-filled battles. He needs your help to determine the smallest possible chaos score for the event, considering all the different ways to pair and organize the warriors. This strategic approach adds an unexpected twist to his love for battles and chaos.

Since the chaos score can get very large, find the result modulo 109 + 7.

Input Format

The first line contains a positive integer n: the number of warriors.
The second line contains a list of n positive integers p; the ith of these represents the Power Level of the ith warrior.
The third line contains a list of n positive integers w; the ith of these represents the Warrior Number of the ith warrior.

Output Format

The minimum possible total that can be attained if warriors are selected optimally. Since the result can be very large, output the result modulo 109 + 7.

Example 1: 

Input:  p = [4, 1, 2], w = [8, 3, 1]
Output: 5 
Explanation:

      

      Let warriors be A, B, and C.
      

      

      Scenario 1:

      First fight between A and B, chaos score = 8

      A is thrown out of arena

      Second fight between B and C, chaos score = 1

      Total chaos score = 8+1 = 9
      

      

      Scenario 2:

      First fight between A and B, chaos score = 8

      B is thrown out of arena

      Second fight between A and C, chaos score = 4

      Total chaos score = 8+4 = 12
      

      

      Scenario 3:

      First fight between A and C, chaos score = 4

      A is thrown out of the arena

      Second fight between B and C, chaos score = 1

      Total chaos score = 4+1 = 5
      

      

      Considering all possible remaining scenarios, we get the minimum chaos score = 5

Example 2: 

Input:  p = [1, 2, 3, 4], w = [10, 20, 30, 40]
Output: 90 
Explanation:

      

      The optimal strategy is to pair the warriors with the lowest power levels with the highest warrior numbers and vice versa. This minimizes the product of each fight's score.
      

      

      First fight between the 1st and 4th warrior, chaos score = 1 * 40 = 40

      Second fight between the 2nd and 3rd warrior, chaos score = 2 * 30 = 60

      Total chaos score = 40 + 60 = 100
      

      

      Since the result can be very large, output the result modulo 109 + 7, which is 100 % (109 + 7) = 90.
Constraints:
    • 2 ≤ n ≤ 103
    • 1 ≤ p[i] ≤ 109
    • 1 ≤ w[i] ≤ 105
Thumbnail 0
Testcase
Result
Case 1

input:

output: