题意
有 n 个商店，每个商店销售 k_i 种物品，每种物品重量为 s_{i,j}，价格为 p_{i,j}，有 c_{i,j} 个。一次购物会从每个商店中选择恰好一个物品，需要满足 m 个限制，形如在商店 x 中选择的物品重量 \le 在商店 y 中选择的物品重量 +w。q 次询问 a_i，求能否进行 a_i 次购物及最小花费。n,k,p\le 30,q\le 10^5。
思路
第一个想法就是直接建立费用流，流量增加 1 就表示一次购物，但这样无法表示限制，所以需要考虑别的方法。注意到这个问题本质上是一个线性规划问题，所以我们先尝试写出线性规划的形式，再考虑怎么处理。记 x_{i,j} 表示商店 i 中第 j 种物品选择了多少个，则需要满足 0\le x_{i,j}\le c_{i,j}，且 \sum_{j\le k_i} x_{i,j}=a，需要最小化 \sum p_{i,j}x_{i,j}。考虑确定了所有 x_{i,j} 之后如何判定能否满足这 m 个限制，显然只要对于任意一对 (x,y) 存在一种安排它们选择的顺序的方式满足限制即可。而这可以看作是问一个二分图上是否有满匹配，可以想到霍尔定理。由于连边的形式是连向一段前缀，所以在按照 s 大小排序之后，只需要考察所有前缀的限制，即对于一对 (u,v)，若 i 是最大的满足 s_{u,i}\le s_{v,j}+w 的 i，那么需要满足 \sum_{k\le i}x_{u,k}\le \sum_{k\le j}x_{v,k}。这样我们就写出了最原始的线性规划形式。
由于求和的项太多了，但都是前缀和，所以我们记新的 x_{i,j} 表示原来的所有 k\le j 的 x_{i,k} 之和，那么限制变为： 0\le x_{i,j}-x_{i,j-1}\le c_{i,j}，x_{i,k_i}=a，x_{u,i}\le x_{v,j}。而第二种限制可以写作 x_{i,k_i}-x_{i,0}=a。这样每个限制都只有两个变量，都是形如 x_i-x_j\le w 的，而最终需要最小化的式子是 \sum p_{i,j}(x_{i,j}-x_{i,j-1})=\sum (p_{i,j}-p_{i,j+1})x_{i,j}，形如 \sum c_ix_i，这样的线性规划问题可以用费用流解决。具体地，将一个 x_i-x_j\le w 的限制改写为 \infty\max(0,x_i-x_j-w) 记入需要最小化的式子中。这样就转化为了 \sum b_ix_i+\sum c_{u,v}\max(x_v-x_u-w_{u,v}) 的形式，这是标准的费用流对偶之后的形式，其等价于要求第 i 个点向外流 b_i 的流量，且每条边 (u,v) 流量为 c_{u,v}，费用为 w_{u,v} 这样网络上的最小费用流。流量限制可以通过新建源汇转变为最小费用最大流，这样就解决了单组询问的问题。
但这样处理不能够支持多次询问 a，因为 a 是作为费用出现的，所以并没有特别好的性质。这里需要一步很巧妙的转化，朴素的处理流量平衡限制的方法是添加源汇，但这里我们不添加源汇，而是利用这张网络的性质来处理掉这个问题。注意到这张网络上连出的边有形如 (i,j)\to(i,j-1) 的流量无穷，费用为 0 的边。而一个点 (i,j) 需要流出 p_{i,j}-p_{i,j+1} 的流量。这可以看作先流出 p_{i,j} 的流量，再流进 p_{i,j+1} 的流量。于是我们可以直接先在 (i,j)\to (i,j-1) 这条边上流 p_{i,j} 的流量，再加上 (i,j-1)\to (i,j) 的流量为 p_{i,j}，费用为 0 的边，表示可以退流。这么流完之后所有流量平衡都被满足了，下面只需要求最小费用循环流。这一步转化将源汇去掉了，求将最小费用最大流转化为最小费用循环流，这其实就是一个找负环的过程，所以就变得简单很多。
再进一步分析一下这张网络可以发现所有的负权边一定是那些连出的 (i,k_i)\to (i,0) 的费用为 -a 的边，所以若想要使得费用减少，必须增广这些边。增加 1 的流量之后，还需要花费 (i,0)\to (i,k_i) 所需要的最小代价把流还回来，所以我们本质上就是在不断增广，直到这个代价 >a 为之。那么这个代价是什么呢？若将所有 (i,0) 看作源点，所有 (i,k_i) 看作汇点，那么增广 f 次就是这张网络上流量为 f 时的最小费用。那么每一次增广增加的代价就是费用流函数的斜率。由于费用流函数是凸的，所以先将凸包求出来之后可以直接二分斜率求解。求凸包可以使用 Primal Dual，复杂度 O(Fn\log n)，最大流量不超过 nkp，所以复杂度 O(n^2kp\log n+q\log n)。
代码