Worst Dot Product

Difficulty: 1400 3500 ms 128 MB

greedy sorting

Reorder B any way you like, then compute ∑ a_i·b_i. Print the MINIMUM 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 minimum dot product over reorderings of B.

Constraints:

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

Sample Tests

3
1 3 -5
-2 4 1

-25

2
1 1
1 1

2

Read the Editorial