〔比赛noip〕猴哥的一天 〔预告 答疑 题解发布〕

人工置顶，顺便透露一下复习一下图论，网络流什么的，有助于最后一题

指导一下不能注册的同学，他会发来一封邮件，你需要将链接中的 手动替换域名contesthunter.org为ch.ezoj.tk

由于第一题太过于简单，于是加入了一道新的题目：猴哥的狗学霸

最后一次人工置顶，今晚7点的比赛，记得准时参加

发一下题面

猴哥的狗学霸
背景
猴哥非常有钱，正因为这样，经常有各个班的超级学霸前来用IQ来换money。
猴哥有n条狗学霸，每个学霸需要做一件事来换取金钱，第i个狗学霸需要猴哥花ai分钟来交代任务，然后学霸们会独立不间断的去完成mission，需要bi分钟，学霸们找到你，选择交代任务的顺序，使得最后一个执行完的任务尽早结束，这样他们可以赚更多的钱
输入格式
第一行为狗学霸个数N；
以下N行为分别为a,b，代表交代任务的时间和任务需要时间；
a,b<=10000；
n<=1000；
输出格式
所有任务完成最短时间
样例输入
第一组
3
2 5
3 2
2 1
第二组
3
3 3
4 4
5 5
样例输出
第一组
8
第二组
15
来源
节操

猴哥的监控系统
背景
在与夷陵的小伙伴们几度交手后，猴哥的计划被一次次击碎，但帝国主义亡我之心依旧不死，现在猴哥对监控中心发动了奇袭，控制了监控中心，一时间夷陵的小伙伴们十分慌张，因为猴哥对监控系统进行了优化，由于猴哥的设备有限，于是他请到了信息组的 坡道的途中 来为其组装监控系统的电控系统，坡道的途中（非fff团员）受到FFF团的指示，全力帮助猴哥
猴哥一共拥有n个监控探头，由于每个监控探头的质量参差不齐，因此组装的成本各不相同：建立第i个监控探头需要的成本为Si（1≤i≤N）
另外猴哥调查得出了所有教室中的情侣群，一共M 个。关于第i 个情侣群的信息概括为Xi, Yi 和Zi：这些情侣会被监控探头Xi 和监控探头Yi 进行全息录像，猴哥有了证据，便可以拆散情侣并获益Zi作为其后续活动的重要经济来源
坡道的途中 可以选择建立一些监控探头，为一些情侣提供“服务”并获得收益。那么如何选择最终建立的监控探头才能让猴哥的获得的后续经费最大呢？ （后续经费= 获益–成本）
输入格式
第一行有两个数N ，M 。
第二行 有N 个数为每一个监控探头的成本，依次为S1 。。。。。。。 Sn
以后M 行 第(i + 2)行 Xi, Yi 和Zi 描述第i 个情侣群情况。
输出格式
猴哥的获得的后续经费
样例输入5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
样例输出
4
数据范围与约定
80%的数据中：N≤200，M≤1 000
100%的数据中：N≤5 000，M≤50 000，0≤Zi≤100，0≤Si≤100。
【时限】2s
来源
编的背景

本次rank1 为一中的vincent

http://pan.baidu.com/s/1dDvjCZn
题解地址

另一张12.31到期的天河影城兑换券已于今天下午2:20送达rank1的一中的vincent