#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include int main() { constexpr int MAX_K = 100000; int n, k; std::cin >> n >> k; std::vector number(n); for (auto& a : number) { std::cin >> a; } std::vector> forward(n), backward(n); forward[0].set(0, true); backward[n - 1].set(k, true); for (auto i = 1; i < n; ++i) { forward[i] = (forward[i - 1] << number[i - 1]) | forward[i - 1]; backward[n - 1 - i] = (backward[n - i] >> number[n - i]) | backward[n - i]; } if (forward.back().test(k - number.back())) { int result{ 0 }; for (auto i = 0; i < n; ++i) { if ((forward[i] & backward[i]).none()) { result += 1; } } std::cout << result << '\n'; } else { std::cout << "-1\n"; } }