[ARC125E] Snack
经典啊，经典。
很容易看出网络流模型：每个人连一个限制 \(c_i\)，每种糖果拆点限流 \(a_i\)，然后每个人向每个糖果连边，最大流就是答案。
考虑转成最小割，我们相当于选出两个集合 \(S \subseteq [1,n], T \subseteq [1,m]\)，割就是 \(\sum_{i \in S} a_i + \sum_{i \notin T}c_i + \sum_{i \in T} (n - |S|)b_i\)。先把中间那项全部加上，那最后就变成了求下面这个东西的最小值。
\[\sum_{i \in S} a_i + \sum_{i \in T} ((n - |S|)b_i - c_i)
\]
前边那部分可以对 \(a\) 排序，后面那部分我们发现一个人选进 \(T\) 时 \(|S|\) 具有单调性，然后直接枚举 \(|S|\) 即可，复杂度 \(O(n \log n)\)。
const int N = 2e5 + 10;
int n, m;
LL a[N], b[N], c[N];
LL tag[N], red[N];
int main() {
read(n, m);
for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 1; i <= m; ++i) read(b[i]);
for(int i = 1; i <= m; ++i) read(c[i]);
for(int i = 1; i <= m; ++i) {
int t = min(c[i] / b[i], 1ll * n);
tag[n - t] += b[i];
red[n - t] += 1ll * t * b[i] - c[i];
}
sort(a + 1, a + n + 1);
LL s = 0, d = 0, ans = 8e18;
for(int i = 1; i <= m; ++i) s += c[i];
for(int i = 0; i <= n; ++i) {
s += a[i] - d + red[i];
d += tag[i];
ans = min(ans, s);
}
printf("%lld\n",ans);
}