Best Dot Product

Difficulty: 1400 3500 ms 128 MB

greedy sorting

Reorder B any way you like, then compute ∑ a_i·b_i. Print the maximum achievable value.

Input: the first line has N; the second line has A's N values; the third line has B's N values.

Output: the maximum dot product over reorderings of B.

Constraints:

• 1 ≤ N ≤ 10⁵
• |values| ≤ 10⁴

Sample Tests

3
1 3 -5
-2 4 1

23

1
-3
2

-6

Read the Editorial