#line 1 "a.cpp" #include #line 2 "/home/huitloxopetl/CP_Library/C++/core/io/output.hpp" #include #line 5 "/home/huitloxopetl/CP_Library/C++/core/io/output.hpp" #include #include #include #include #ifndef TEMPLATE using i128 = __int128_t; using u128 = __uint128_t; #endif namespace IO { std::ostream &operator<<(std::ostream &dest, const i128 &value) { std::ostream::sentry s(dest); if(s) { u128 tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while(tmp != 0); if(value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if(dest.rdbuf() -> sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } template std::ostream& operator<<(std::ostream &os, const std::pair &p){ os << p.first << ' ' << p.second; return os; } template std::ostream& operator<<(std::ostream &os, const std::array &a){ if(a.size()){ os << a.front(); for(auto i=a.begin(); ++i!=a.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::vector &v){ if(v.size()){ os << v.front(); for(auto i=v.begin(); ++i!=v.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::map &m){ if(m.size()){ os << m.begin()->first << ' ' << m.begin()->second; for(auto i=m.begin(); ++i!=m.end();){ os << '\n' << i->first << ' ' << i->second; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::set &st){ if(st.size()){ os << *st.begin(); for(auto i=st.begin(); ++i!=st.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::multiset &ms){ if(ms.size()){ os << *ms.begin(); for(auto i=ms.begin(); ++i!=ms.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::deque &dq){ if(dq.size()){ os << dq.front(); for(auto i=dq.begin(); ++i!=dq.end();){ os << ' ' << *i; } } return os; } inline void out(){ std::cout << '\n'; } template inline void out(const T& x){ std::cout << x << '\n'; if(flush) std::cout.flush(); } template inline void out(const Head& head, const Tail&... tail){ std::cout << head << ' '; out(tail...); } template inline void vout(const T& v){ std::cout << v << '\n'; if(flush) std::cout.flush(); } template inline void vout(const std::vector& v){ for(const auto &el: v) std::cout << el << '\n'; if(flush) std::cout.flush(); } template inline void vout(const Head& head, const Tail&... tail){ std::cout << head << '\n'; vout(tail...); } #define fin(...) do{ out(__VA_ARGS__); return; }while(false) } // IO #if local //https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3 #include #else #define dump(...) static_cast(0) #endif /** * @brief 出力 */ #line 3 "a.cpp" using namespace IO; template inline bool chmax(T& a, const U& b) { if(a < b) { a = b; return true; } return false; } int main() { std::cin.tie(nullptr) -> sync_with_stdio(false); int n, k; int64_t p; std::cin >> n >> p >> k; const auto chk = [](const __int128_t x) -> bool { return x > int64_t(1e18); }; std::vector dp(n + 1, std::vector(k + 1, __int128_t(0))); dp[0][0] = p; for(int i = 0; i < n; ++i) { int t, b; std::cin >> t >> b; for(int j = 0; j < k; ++j) { if(t == 1) { const auto x = dp[i][j] + b; if(chk(x)) { std::cout << -1 << '\n'; std::exit(0); } chmax(dp[i + 1][j + 1], x); } else { const auto x = dp[i][j] * 2; if(chk(x)) { std::cout << -1 << '\n'; std::exit(0); } chmax(dp[i + 1][j + 1], x); } chmax(dp[i + 1][j], dp[i][j]); } } std::cout << dp[n][k] << '\n'; }