TX202607 图书馆还书队列

题目描述

图书馆只有一个还书窗口，现在有 N 名学生等待还书。

第 i 名学生办理还书手续需要 t_i 分钟。由于每名学生后续的安排不同，他们每等待一分钟产生的等待代价也不同：第 i 名学生每等待一分钟，会产生 w_i 点等待代价。

图书管理员可以重新安排所有学生的办理顺序。

办理从第 0 分钟开始。每次只能为一名学生办理手续，一旦开始，就必须完成该学生的全部手续，才能为下一名学生办理。两名学生之间不安排空闲时间。

一名学生的等待时间，是从第 0 分钟到开始为他办理手续之间经过的时间，不包含他自己的办理时间。

因此，第 i 名学生产生的等待代价为：

等待时间 × w_i

请你安排办理顺序，使所有学生产生的等待代价之和最小，并输出这个最小值。

输入格式

第一行包含一个正整数 N，表示学生人数。

接下来 N 行，每行包含两个正整数 t_i 和 w_i，分别表示第 i 名学生的办理时间和每分钟等待代价。

输出格式

输出一个整数，表示所有学生等待代价之和的最小值。

样例输入

3
3 1
1 4
2 2

样例输出

5

样例说明

可以按照第 2、3、1 名学生的顺序办理：

总等待代价为 0 + 2 + 3 = 5。

数据范围

• 1 ≤ N ≤ 10^5
• 1 ≤ t_i ≤ 10^4
• 1 ≤ w_i ≤ 10^4

子任务如下，各子任务独立计分：