/* -*- coding: utf-8 -*- * * 949.cc: No.949 飲酒プログラミングコンテスト - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 3000; /* typedef */ struct Elm { int d, i; Elm() {} Elm(int _d, int _i): d(_d), i(_i) {} bool operator<(const Elm &e) const { return d < e.d || (d == e.d && i > e.i); } }; /* global variables */ int as[MAX_N + 1], bs[MAX_N + 1], ds[MAX_N]; Elm dp[MAX_N + 1][MAX_N + 1]; /* subroutines */ template inline void setmax(T &a, T b) { if (a < b) a = b; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i <= n; i++) scanf("%d", as + i); for (int i = 0; i <= n; i++) scanf("%d", bs + i); for (int i = 0; i < n; i++) scanf("%d", ds + i); sort(ds, ds + n); for (int i = 0; i <= n; i++) fill(dp[i], dp[i] + n + 1, Elm(0, n)); for (int i = 0; i < n; i++) for (int j = 0; i + j < n; j++) { Elm &dp0 = dp[i][j]; if (dp0.i > 0) { int ki = upper_bound(ds, ds + dp0.i, as[i + 1] + bs[j]) - ds - 1; setmax(dp[i + 1][j], (ki < dp0.i) ? Elm(dp0.d + (ki >= 0 ? 1 : 0), ki) : dp0); int kj = upper_bound(ds, ds + dp0.i, as[i] + bs[j + 1]) - ds - 1; setmax(dp[i][j + 1], (kj < dp0.i) ? Elm(dp0.d + (kj >= 0 ? 1 : 0), kj) : dp0); } else { setmax(dp[i + 1][j], dp0); setmax(dp[i][j + 1], dp0); } } int maxd = 0; for (int i = 0; i <= n; i++) setmax(maxd, dp[i][n - i].d); printf("%d\n", maxd); return 0; }