3919 - 汤圆

题目描述

春节将近,小 A 的汤圆生产厂最近接了一批紧急订单,需要生产柿子造型的汤圆,芝麻汤圆,黄米汤圆等等。

但是目前只剩一条生产线可供使用,所有订单共用一条生产线,同一时刻只能加工一个订单。每个订单都需要在设备上连续加工一段时间。订单一旦开始就不能中断,但如果在等待期间或加工过程中,订单会不断产生“订单压力值”。

具体来说,第 i 个订单需要连续加工 t_i 个时间单位才能完成。在它未完成之前的每一时刻(包括等待开始的时间和正在加工的时间),都会以固定速率产生“订单压力值” p_i。如果一个订单在第 T 个时间单位结束时才完成,那么该订单产生的总压力值为 p_i \times T。整个生产过程的总压力值为所有订单产生压力值的总和

请帮帮小 A,如何安排订单的完成顺序,使得整个过程中产生的总压力值最小?

输入

第一行:一个整数 n

第二行到第 n+1 行:第 i 行有两个整数表示 t_ip_i

输出

单个整数:表示整个过程中产生的最小总压力值。

样例

输入

3
3 1
2 2
1 3

输出

15

输入

4
4 5
3 4
2 3
1 2

输出

85

输入

5
2 1
3 1
4 1
5 1
6 1

输出

50
说明

样例 1 解释

最小订单压力值的方案可以按照订单3 \rightarrow 订单2 \rightarrow 订单1 的顺序一次完成。

  • 订单 3 在第 1 个时间单位完成,产生压力值:3 \times 1 = 3
  • 订单 2 在第 1+2=3 个时间单位完成,产生压力值:2 \times 3 = 6
  • 订单 1 在第 1+2+3=6 个时间单位完成,产生压力值:1 \times 6 = 6

总订单压力值为:3 + 6 + 6 = 15

数据规模

对于 30\% 的数据,满足 1≤n≤15

对于 60\% 的数据,满足 1≤n≤5000

对于 100\% 的数据,满足 1≤n≤200,0001 ≤ t_i ≤ 200,0001 ≤ p_i ≤ 200,000

数据保证最终的结果在 10^{18} 以内。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 17
通过人数 6
金币数量 2 枚
难度 入门


上一题 下一题