#P765. 维修安排

维修安排

题目描述

小爱同时接受了 nn 份维修任务。完成第 ii 份维修任务需要 tit_i 的时间才能完成,这个维修任务在没有完成之前,每个单位时间会收到 fif_i 个单位的损失。

请问小爱应该以什么顺序完成这些任务,才能让损失总量达到最小?

输入格式

  • 第一行:单个整数 nn
  • 第二行到第 i+1i+1 行:第 ii 行有两个整数表示 tit_ifif_i

输出格式

  • 单个整数:表示最少损失总额。
3
3 1
1 3
2 2
15

样例解释 1

先做最短时间就能完成的任务

2
9 10
8 9
242

数据范围

  • 30%30\% 的数据,1n151\leq n\leq 15
  • 60%60\% 的数据,1n50001\leq n\leq 5000
  • 100%100\% 的数据,1n200,0001\leq n\leq 200,000
  • 1ti200,0001\leq t_i\leq 200,000
  • 1fi200,0001\leq f_i\leq 200,000