#include #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define REP(i,n) for(int i=0;i<(n);i++) #define fi first #define se second #define pb push_back #define mp make_pair using namespace std; typedef pair pii; typedef vector vi; typedef long long ll; template void read(T &x){ int f=0; x=0; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) f|=(ch=='-'); for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; if(f) x=-x; } const int N=2005; const ll inf=1e18; ll f[N][N],a[N],b[N],sa[N],sb[N]; int n; void cmin(ll &x,ll y){ if(y=inf) continue; cmin(f[i][j],f[i-1][j]); if(sb[i]>=f[i-1][j]+a[i]){ cmin(f[i][j+1],f[i-1][j]+a[i]); } } } int k=0; while(f[n][k+1]