UVA10983 Buy one, get the rest free

【问题描述】 有 N 个城市，每个城市都有一些选手要到第 N 个城市去参加比赛。比赛的组织者可以租用城市之间的一些飞机，他们的出发时间可能不同，但是都是从某天晚上出发，然后第二天早上到达目的地，每架飞机上都有载客上限和租金。现在有一个优惠：只要租用一架飞机，就可以免费使用所有价格小于等于该租金的飞机。组织者希望在 d 天内花最少的钱把所有的选手送到比赛地。 比如说，有 4 架飞机，租金分别是 10000，25000，30000，40000，你租下 30000 元的那架，那么就可以免费使用 10000 和 25000 的那架。相当于租下 3 架飞机的费用就是 30000。



对于 30%的数据，$2≤n≤200$,$n-1≤m≤200$,$1≤wi≤1000$,$1≤ci≤1000$，$1≤ai,bi≤n$, $ai≠bi$,$0≤S≤10^5$ 对于100%的数据，$2≤n≤2*10^5$,$n-1≤m≤2*10^5$，$1≤wi≤10^9$，$1≤ci≤10^9$，$1≤ai$,$bi≤n$,$ai≠bi$，$0≤S≤10$ 感谢@durex_com 提供的翻译