第 \(i\) 种球有 \(a_i\) 个，共 \(n\) 种。
第 \(i\) 种箱子最多共装 \(b_i\) 个球。共 \(m\) 种。
第 \(i\) 种球在第 \(j\) 种箱子里至多放 \(ij\) 个。
问所有箱子放的球数最多是多少。
\(1\leq n\leq 500,1\leq m\leq 5e5,0\leq a_i,b_i\leq 1e12\)。
很容易建出网络流模型。从上至下依次有 \(1,n,m,1\) 个点。但是图实在太大了。
考虑求最小割。那就是要把上下共 \(n+m\) 个点划分为两类。
将它表示出来。设上下的全集分别为 \(X=\{1,2,...,n\},Y=\{1,2,...,m\}\)。
上下分别选了 \(P\subseteq X,Q\subseteq Y\) 归于源点集合。（以下所有式子所有求和条件略去这两个）
这个东西的最小值不好求。因为既要考虑 \(P\) 也要考虑 \(Q\)。
观察到数据范围很小，考虑枚举一点东西来把问题划分成独立的两个问题。枚举中间项左侧的 \(k=\sum_{i\in X}i\)。
有 \(0\leq k\leq n(n+1)/2\)。
那么对最左项的限制就是选一些求和为 \(k\) 的 \(i\)，作为 \(P\)。剩下的 \(a_i\) 加起来作为这一项。
写在求和的条件上就是：
下面一行要么纳入源点集合，在第三项计算。否则在第二项计算。
发现此时下面一行对于是否纳入源点集合不受约束。贪心地让它取较小的，使得整个式子最小。
那么可以分别求出左侧和右侧对于每个 \(k\) 的最小值，相加。
左侧可以用 \(O(n^3)\) 的 DP 算出，右侧可以发挥智慧写出 \(O(n^2+m)\)。这部分比较简单。
总时间复杂度为 \(O(n^3+m)\)。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rg register
#define ld long double
#define ull unsigned long long
#define gc getchar
#define pc putchar
#define pob pop_back
#define ump unordered_map
#define vi vector<int>
#define vl vector<ll>
#define fo(i,l,r) for(rg int i=(l);i<=(r);++i)
using namespace std;
inline int re() {
rg int x=0,p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline ll rel() {
rg ll x=0;rg int p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline void wt(rg int x) { if(x>9) wt(x/10);pc(x%10+48); }
inline void wtl(rg ll x) { if(x>9) wtl(x/10);pc(x%10+48); }
const int N=505;
const int M=5e5+5;
const ll inf=1e18;
int n,m;
ll a[N],b[M],f[N*(N+1)/2],ans=inf;
ll minl(ll a,ll b) { return a<b?a:b; }
struct pr { ll t;int i; }c[M];
bool cmp_by_t(pr a,pr b) { return a.t<b.t; }
int main() {
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=re(),m=re();
fo(i,1,n) {
a[i]=rel();
}
fo(i,1,m) {
b[i]=rel();
}
vector<vl>f(n+1,vl(n*(n+1)/2+1,inf));
int sum=0;
f[0][0]=0;
fo(i,0,n-1) {
for(int j=sum;j>=0;j--) {
f[i+1][j+i+1]=minl(f[i+1][j+i+1],f[i][j]);
f[i+1][j]=minl(f[i+1][j],f[i][j]+a[i+1]);
}
sum+=i+1;
}
ll s1=0,s2=0,si=0;
fo(i,1,m) {
si+=i;
c[i].t=b[i]/i;
c[i].i=i;
// printf("%d : %d\n",i,c[i].t);
}
sort(c+1,c+m+1,cmp_by_t);
int z=1;
fo(k,0,n*(n+1)/2) {
// printf("%d : %lld %lld %lld\n",k,s1,s2,f[n][k]);
ans=minl(ans,f[n][k]+s1+s2);
while(z<=m&&c[z].t==k) {
s1-=1ll*k*c[z].i;
s2+=b[c[z].i];
si-=c[z].i;
z++;
}
s1+=si;
}
wtl(ans);
}