#include #include #include #include // アルゴリズム static inline constexpr std::vector solve(const uint_least32_t N, const uint_least32_t W, const std::vector& v, const std::vector& w) noexcept { // 動的計画法パート std::vector>> dp(N + 1, std::vector>(W + 1, { 0, UINT_LEAST32_MAX })); // 後ろから見ていく for (int_least32_t i = N - 1; i >= 0; --i) { for (uint_least32_t j = 0; j != w[i]; ++j) dp[i][j] = dp[i + 1][j]; for (uint_least32_t j = w[i]; j <= W; ++j) { // ご利益が等しいなら、選ばない方が良い if (dp[i + 1][j].first >= dp[i + 1][j - w[i]].first + v[i]) dp[i][j] = dp[i + 1][j]; else dp[i][j] = { dp[i + 1][j - w[i]].first + v[i], i + 1 }; } } // トレースバック(遡及)パート std::vector ans; for (uint_least32_t i = dp[0][W].second, budget = W; i != UINT_LEAST32_MAX; budget -= w[i - 1], i = dp[i][budget].second) ans.push_back(i); return ans; } // 出力 static inline void output(const std::vector& ans) noexcept { std::cout << ans.size() << '\n' << ans[0]; for (uint_least32_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); uint_least32_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; }