#include #include #include #include // アルゴリズム static inline constexpr std::vector solve(const uint_fast32_t N, const uint_fast32_t W, const std::vector& v, const std::vector& w) noexcept { // 動的計画法パート std::vector> dp_value(N + 1, std::vector(W + 1, 0)); std::vector> dp_next(N + 1, std::vector(W + 1, UINT_FAST32_MAX)); // 後ろから見ていく for (int_fast32_t i = N - 1; i >= 0; --i) { for (uint_fast32_t j = 0; j != w[i]; ++j) dp_value[i][j] = dp_value[i + 1][j], dp_next[i][j] = dp_next[i + 1][j]; for (uint_fast32_t j = w[i]; j <= W; ++j) { // ご利益が等しいなら、選ばない方が良い if (dp_value[i + 1][j] >= dp_value[i + 1][j - w[i]] + v[i]) dp_value[i][j] = dp_value[i + 1][j], dp_next[i][j] = dp_next[i + 1][j]; else dp_value[i][j] = dp_value[i + 1][j - w[i]] + v[i], dp_next[i][j] = i + 1 ; } } // トレースバック(遡及)パート std::vector ans; for (uint_fast32_t i = dp_next[0][W], budget = W; i != UINT_FAST32_MAX; budget -= w[i - 1], i = dp_next[i][budget]) ans.push_back(i); return ans; } // 出力 static inline void output(const std::vector& ans) noexcept { std::cout << ans.size() << '\n' << ans[0]; for (uint_fast32_t i = 1; i != ans.size(); ++i) std::cout << ' ' << ans[i]; std::cout << '\n'; } // 入力 int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint32_t N, W, i; std::cin >> N >> W; std::vector v(N), w(N); for (i = 0; i != N; ++i) std::cin >> v[i]; for (i = 0; i != N; ++i) std::cin >> w[i]; output(solve(N, W, v, w)); return 0; }