春节将近,小 A 的汤圆生产厂最近接了一批紧急订单,需要生产柿子造型的汤圆,芝麻汤圆,黄米汤圆等等。
但是目前只剩一条生产线可供使用,所有订单共用一条生产线,同一时刻只能加工一个订单。每个订单都需要在设备上连续加工一段时间。订单一旦开始就不能中断,但如果在等待期间或加工过程中,订单会不断产生“订单压力值”。
具体来说,第 i 个订单需要连续加工 t_i 个时间单位才能完成。在它未完成之前的每一时刻(包括等待开始的时间和正在加工的时间),都会以固定速率产生“订单压力值” p_i。如果一个订单在第 T 个时间单位结束时才完成,那么该订单产生的总压力值为 p_i \times T。整个生产过程的总压力值为所有订单产生压力值的总和。
请帮帮小 A,如何安排订单的完成顺序,使得整个过程中产生的总压力值最小?
第一行:一个整数 n。
第二行到第 n+1 行:第 i 行有两个整数表示 t_i 与 p_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
最小订单压力值的方案可以按照订单3 \rightarrow 订单2 \rightarrow 订单1 的顺序一次完成。
总订单压力值为:3 + 6 + 6 = 15。
对于 30\% 的数据,满足 1≤n≤15。
对于 60\% 的数据,满足 1≤n≤5000。
对于 100\% 的数据,满足 1≤n≤200,000,1 ≤ t_i ≤ 200,000,1 ≤ p_i ≤ 200,000。
数据保证最终的结果在 10^{18} 以内。