旅游安排¶
- 参考时间限制：6.0 秒（评测环境与性能）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
背景故事¶
方块小镇准备组织一次村际旅行。居民只对离家较近的村子感兴趣，各村接待游客的名额也有限。旅行中的消费太多还会拖慢服务器，因此组织者希望先让尽可能多的人出游，再尽量降低总消费。
小镇有些旅游道路带有时间旅行装置，记录的距离可能是负数。请先检查道路是否存在负环，再安排游客。
形式化问题描述¶
有 \(n\) 个村子和 \(m\) 条有向道路。道路 \(u\to v\) 的长度为 \(w\) . 若道路图的任意位置存在总长度为负的有向环，直接报告负环。
否则，令 \(d(i,j)\) 为从村子 \(i\) 到村子 \(j\) 的最短路长度。村子 \(i\) 的候选目的地为所有可从 \(i\) 到达且不同于 \(i\) 的村子。按数对
从小到大排序，先比较最短路长度，再比较编号差的绝对值。村子 \(i\) 的居民对前 \(k_i\) 个候选目的地感兴趣；若第 \(k_i\) 名与后面的目的地在这两个量上都相同，并列者全部入选。候选目的地不足 \(k_i\) 个时全部入选；\(k_i=0\) 时没有感兴趣的目的地。
村子 \(i\) 有 \(V_i\) 名希望旅行的居民，每人出游会消费 \(C_i\) 次。村子 \(j\) 最多接待 \(H_j\) 名外来游客，每次消费的价格为 \(P_j\) . 一名村子 \(i\) 的居民前往村子 \(j\) 时，产生 \(C_iP_j\) 的费用。
每位居民最多前往一个自己感兴趣的目的地。未出游者留在本村，不占接待名额，也不产生费用。道路只用于确定目的地的远近，不限制游客流量，也不额外收费。
在出游人数最大化的前提下，求总费用的最小值。
输入格式¶
第一行两个整数 \(n,m\) .
接下来 \(m\) 行，每行三个整数 \(u,v,w\) ，表示一条从 \(u\) 到 \(v\) 的有向道路。
接下来 \(n\) 行，第 \(i\) 行五个整数 \(k_i,V_i,C_i,H_i,P_i\) .
输出格式¶
若道路图存在负环，输出一行 Negative loop found.（包括末尾英文句号）。否则输出一行整数，表示最大出游人数下的最小总费用。没有人能够出游时输出 \(0\) .
样例 1¶
输入¶
4 6
1 2 1
1 3 2
1 4 3
2 3 -1
2 4 3
3 4 7
3 3 2 0 0
2 2 3 2 5
1 4 1 2 3
0 0 0 1 10
输出¶
45
样例 2¶
输入¶
2 2
1 2 1
2 1 -2
3 3 2 0 0
2 2 3 2 5
输出¶
Negative loop found.
样例 3¶
输入¶
3 2
2 1 1
2 3 1
0 0 0 1 7
1 2 1 0 0
0 0 0 1 11
输出¶
18
样例解释¶
样例 1 的总接待名额为 \(5\) . 让村子 \(1\) 向村子 \(2\) 派 \(2\) 人、向村子 \(3\) 派 \(1\) 人，再让村子 \(2\) 向村子 \(3\) 派 \(1\) 人、村子 \(3\) 向村子 \(4\) 派 \(1\) 人，便可安排 \(5\) 人出游，总费用为 \(20+6+9+10=45\) .
样例 2 的环 \(1\to2\to1\) 总长度为 \(-1\) .
样例 3 中，村子 \(1\) 和 \(3\) 对村子 \(2\) 的排名并列，即使 \(k_2=1\) ，二者仍都入选。两名游客各去一个目的地，总费用为 \(7+11=18\) .
数据范围与保证¶
对 100% 的数据：\(1\le n\le1000\) ，\(1\le m\le5000\) ；每条道路满足 \(1\le u,v\le n\) 、\(u\ne v\) 、\(-10^9\le w\le10^9\) . 允许多条道路连接同一对有序端点。
对每个村子：\(0\le k_i\le10\) ，\(0\le V_i,H_i\le10^9\) ，\(0\le C_i,P_i\le30\) . 所有输入量均为整数。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |