#include #include #include #include #include #include using namespace std; using default_counter_t = int64_t; // macro #define let auto const& #define overload4(a, b, c, d, name, ...) name #define rep1(n) \ for (default_counter_t i = 0, end_i = default_counter_t(n); i < end_i; ++i) #define rep2(i, n) \ for (default_counter_t i = 0, end_##i = default_counter_t(n); i < end_##i; \ ++i) #define rep3(i, a, b) \ for (default_counter_t i = default_counter_t(a), \ end_##i = default_counter_t(b); \ i < end_##i; ++i) #define rep4(i, a, b, c) \ for (default_counter_t i = default_counter_t(a), \ end_##i = default_counter_t(b); \ i < end_##i; i += default_counter_t(c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(n) \ for (default_counter_t i = default_counter_t(n) - 1; i >= 0; --i) #define rrep2(i, n) \ for (default_counter_t i = default_counter_t(n) - 1; i >= 0; --i) #define rrep3(i, a, b) \ for (default_counter_t i = default_counter_t(b) - 1, \ begin_##i = default_counter_t(a); \ i >= begin_##i; --i) #define rrep4(i, a, b, c) \ for (default_counter_t \ i = (default_counter_t(b) - default_counter_t(a) - 1) / \ default_counter_t(c) * default_counter_t(c) + \ default_counter_t(a), \ begin_##i = default_counter_t(a); \ i >= begin_##i; i -= default_counter_t(c)) #define rrep(...) \ overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define ALL(f, c, ...) \ (([&](decltype((c)) cccc) { \ return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); \ })(c)) // function template constexpr C& Sort(C& a) { std::sort(std::begin(a), std::end(a)); return a; } template constexpr auto& Min(C const& a) { return *std::min_element(std::begin(a), std::end(a)); } template constexpr auto& Max(C const& a) { return *std::max_element(std::begin(a), std::end(a)); } template constexpr auto Total(C const& c) { return std::accumulate(std::begin(c), std::end(c), C(0)); } template auto CumSum(std::vector const& v) { std::vector a(v.size() + 1, T(0)); for (std::size_t i = 0; i < a.size() - size_t(1); ++i) a[i + 1] = a[i] + v[i]; return a; } template constexpr bool ChMax(T& a, T const& b) { if (a < b) { a = b; return true; } return false; } template constexpr bool ChMin(T& a, T const& b) { if (b < a) { a = b; return true; } return false; } void In(void) { return; } template void In(First& first, Rest&... rest) { cin >> first; In(rest...); return; } template void VectorIn(vector& v, const I n) { v.resize(size_t(n)); rep(i, v.size()) cin >> v[i]; } void Out(void) { cout << "\n"; return; } template void Out(First first, Rest... rest) { cout << first << " "; Out(rest...); return; } constexpr auto yes(const bool c) { return c ? "yes" : "no"; } constexpr auto Yes(const bool c) { return c ? "Yes" : "No"; } constexpr auto YES(const bool c) { return c ? "YES" : "NO"; } // http://koturn.hatenablog.com/entry/2018/08/01/010000 template inline std::vector MakeNdVector(T n, U val) noexcept { static_assert(std::is_integral::value, "[MakeNdVector] The 1st argument must be an integer"); return std::vector(std::forward(n), std::forward(val)); } template inline decltype(auto) MakeNdVector(T n, Args&&... args) noexcept { static_assert(std::is_integral::value, "[MakeNdVector] The 1st argument must be an integer"); return std::vector(args)...))>( std::forward(n), MakeNdVector(std::forward(args)...)); } template 0), std::nullptr_t>::type = nullptr> struct NdvectorImpl { using type = std::vector::type>; }; // struct ndvector_impl template struct NdvectorImpl { using type = std::vector; }; // struct ndvector_impl template using NdVector = typename NdvectorImpl::type; #ifdef USE_STACK_TRACE_LOGGER #ifdef __clang__ #pragma clang diagnostic push #pragma clang diagnostic ignored "-Weverything" #include #pragma clang diagnostic pop #endif //__clang__ #endif // USE_STACK_TRACE_LOGGER signed main(int argc, char* argv[]) { (void)argc; #ifdef USE_STACK_TRACE_LOGGER google::InitGoogleLogging(argv[0]); google::InstallFailureSignalHandler(); #else (void)argv; #endif // USE_STACK_TRACE_LOGGER int64_t N; In(N); vector A(N + 1), B(N + 1), D(N); rep(i, N + 1) In(A[i]); rep(i, N + 1) In(B[i]); rep(i, N) In(D[i]); auto dp = MakeNdVector(N + 1, N + 1, int64_t(N)); ALL(sort, D, greater()); dp[0][0] = -1; rep(i, N) { rep(j, i + 1) { if (dp[i][j] + 1 >= N) continue; auto func = [&](const int64_t l, const int64_t ab) { int64_t m = (dp[i][j] < 0 ? 1000000 : D[dp[i][j]]); ChMin(m, ab); int64_t k = lower_bound(D.begin() + (dp[i][j] + 1), D.end(), m, greater()) - D.begin(); ChMin(dp[i + 1][l], k); }; func(j, A[j] + B[i - j + 1]); if (j + 1 <= N) func(j + 1, A[j + 1] + B[i - j]); } } int64_t ans = 0; rep(i, N + 1) { rep(j, i + 1) { if (dp[i][j] < N) { ChMax(ans, i); } } } cout << ans << endl; return EXIT_SUCCESS; }