我们可以把整个工作流程想像成网络流上的一条链：第\(i\)天连接到第\(i+1\)天的，流量为\(INF – A_i\)，费用为\(0\)；其中第\(n+1\)连接到汇点，流量为\(INF\)，费用为\(0\)；源点连接到点\(1\)，流量为\(INF\)，费用为\(0\)。
对于每一组志愿者\((s_i, t_i, c_i)\)，考虑连边\((s_i, t_i + 1, INF, c_i)\)，这样意味着整个工作流中可以从额外管道中获取流量，将最大流调整到\(INF\)。
所以求得的最小费用肯定是在最大流量\(INF\)的前提下求得的，即为答案。
大水题。
考虑按照给定数据建一张费用全部为 0 的图。跑完费用流求最大流输出答案之后，在现有的边的基础上加一条方向一致、容量无限、费用为\(w_i\)的边，最后开一个新点连接点\(n\)，容量为\(k\)即可。
首先我们在\(Q\)的剩余系内枚举数\(x_0\)，对于此每个数表示成\(x = (x_0 + k * P) \mod Q\)，思考一下发现这些数会随着\(k\)变化，且这些数会呈现周期性规律：也就是这些数在一个环上，我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献，记录成前缀和，计算答案时比较排名来判断环的方向（长弧或是短弧）。
具体看代码吧，细细品味一下应该就能理解了。
这道题是一道裸题，考察莫比乌斯反演和 Dirichlet 卷积的知识。
在这里我们规定\(n<m\)，这两者调换不会对答案产生影响。然后我们来观察这个计数规律，发现每一个点对答案的贡献至少为\(1\)，附加的贡献其实就是当前线段上除了本身的整点（整数坐标点）个数的两倍，换句话说就是：
\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]
一开始毫无头绪，在看了题解之后豁然开朗（废话，看了题解不都豁然开朗么）。题目中要求我们求出：
\[ ans = \underbrace{ \sum_{a_1 = L}^R \dots \sum_{a_n = L}^R }_{n \text{ 个}} [\gcd_{i = 1}^n (a_i) = k] \]
题意就是要求：
\[ ( \sum_{i = 1}^n \sum_{j = 1}^n ij gcd(i, j) ) \mod p \]
言简意赅的题面非常舒适。出现了\(gcd\)可以考虑往反演方面思考。先进行例行的套路：枚举\(gcd\)。在这里为了书写方便，我就把取模省去。