#include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) typedef long long ll; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define INF 2140000000 const long long MOD = 1000000007; //const long long MOD = 998244353; using namespace std; int dp[3005][3005]; int main(int argc, char* argv[]) { int n; scanf("%d", &n); vector a(n+1),b(n+1),d(n); int i,j; for(i=0; i1) { int m=(l+r)/2; for(i=0; i<=n; i++) { for(j=0; j<=n; j++) { dp[i][j]=0; } } dp[0][0]=1; int k; for(k=1; k<=m; k++) { int found=0; for(i=0; i<=k; i++) { int j=k-i; if((i>0 && dp[i-1][j])||(j>0 && dp[i][j-1])) { if(a[i]+b[j]>=d[m-k]) { dp[i][j]=1; found=1; } } } if(found==0) break; } if(k==m+1) { //ok l=m; } else { r=m; } } printf("%d\n", l); return 0; }