Problem Description

Score: $ 700 $ points

T-san is an angel who has come down from the heavenly realm to study the mundane world. Today, she is studying the Japanese-style room while helping out at a certain mansion, and the owner has asked her to close the fusuma (sliding doors).

This beautiful mansion has $ N $ fusuma numbered from $ 1 $ to $ N $. Each fusuma is a work of art, so they each have different widths and weights. Some are very heavy, and T-san is worried that she might run out of strength.

Currently, the $ N $ fusuma are aligned at one end of the room. The width of fusuma $ i $ is $ A_i $, and its weight is $ B_i $. The total width of all the fusuma is equal to the width of the room divider (the width within which the fusuma can be moved). She consumes $ xy $ stamina when moving a fusuma of weight $ x $ for a distance of length $ y $.

For the worrywart T-san, calculate the minimum total stamina required to completely close all the fusuma.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ A_3 $ $ B_3 $ ... $ A_N $ $ B_N $

Output Format

Output the minimum stamina required for T-san to completely close all the fusuma.

Sample Input and Output

Sample Input #1

3
2 1
5 3
3 4

Sample Output #1

17

Sample Input #2

5
5 4
4 3
2 4
4 2
1 1

Sample Output #2

62

Notes/Hints

Constraints

• $ N $ is an integer between $ 1 $ and $200\ 000$ inclusive.
• $ A_i $, $ B_i $ ($1 \leq i \leq N$) are integers between $ 1 $ and $10\ 000$ inclusive.

Subtasks

Subtask 1 \[ $ 200 $ points \]

• $N \leq 10$

Subtask 2 \[ $ 500 $ points \]

• No additional constraints.

Sample Explanation 1

As shown in the figure above, if the fusuma are arranged in the order (fusuma $ 3 $) -> (fusuma $ 2 $) -> (fusuma $ 1 $), the required stamina is $ 0 * 4 + 3 * 3 + (3 + 5) * 1 = 17 $.

Sample Explanation 2

If the fusuma are arranged in the order (fusuma $ 3 $) -> (fusuma $ 5 $) -> (fusuma $ 1 $) -> (fusuma $ 2 $) -> (fusuma $ 4 $), the required stamina is $ 0 * 4 + 2 * 1 + 3 * 4 + 8 * 3 + 12 * 2 = 62 $.

见题面 Input 部分

见题面 Output 部分