// Problem: U736917 Yet Another Knapsack Problem
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/U736917
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
// #include <bits/extc++.h>
#define multiple_cases(T) signed T; cin >> T; while (T--)
#define variable_name(x) #x
#define all(x) (x).begin(), (x).end()
#define adebug(a, b, c) #a << "[" << (b) << "..." << (c) << "] = " << vector<typename decay<decltype(*((a) + (b)))>::type>((a) + (b), (a) + (c) + 1)
#define file_io(a) (freopen(#a ".in", "r", stdin), freopen(#a ".out", "w", stdout))
#ifdef assert
#undef assert
#endif
#define assert(x) if (!(x)) { std::cerr << "Assertion failed: " << #x << ", line " << __LINE__ << std::endl; exit(1); } else;
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
const int mod = 998244353;
template<typename T, typename Tb>
T quickpower(T a, Tb b) {
	if (b < 0) b = b % (mod - 1) + mod - 1;
	T c = 1;
	while (b) {
		if (b & 1) {
			c *= a;
			c %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return c;
}
template<typename T, typename Tb>
T auto_quickpower(T a, Tb b) {
	T c = 1;
	while (b) {
		if (b & 1) {
			c *= a;
		}
		a *= a;
		b >>= 1;
	}
	return c;
}
namespace quick_io {
	template<typename... Args>
	ostream& operator<<(ostream& os, const tuple<Args...>& t);
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const vector<T, Alloc> &b);
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const deque<T, Alloc> &b);
	template<typename T1, typename T2>
	ostream &operator<<(ostream &A, const pair<T1, T2> &b);
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const set<T, Compare, Alloc> &b);
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multiset<T, Compare, Alloc> &b);
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const map<T, T2, Compare, Alloc> &b);
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multimap<T, T2, Compare, Alloc> &b);
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_set<T, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multiset<T, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_map<T, T2, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multimap<T, T2, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const vector<T, Alloc> &b) {
		A << "[";
		for (typename vector<T, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "]";
	}
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const deque<T, Alloc> &b) {
		A << "[";
		for (typename deque<T, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "]";
	}
	template<typename T1, typename T2>
	ostream &operator<<(ostream &A, const pair<T1, T2> &b) {
		return A << '(' << b.first << ',' << b.second << ')';
	}
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const set<T, Compare, Alloc> &b) {
		A << "{";
		for (typename set<T, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multiset<T, Compare, Alloc> &b) {
		A << "{";
		for (typename multiset<T, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const map<T, T2, Compare, Alloc> &b) {
		A << "{";
		for (typename map<T, T2, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multimap<T, T2, Compare, Alloc> &b) {
		A << "{";
		for (typename multimap<T, T2, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_set<T, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_set<T, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multiset<T, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_multiset<T, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_map<T, T2, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_map<T, T2, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multimap<T, T2, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_multimap<T, T2, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	void print_tuple(ostream&, const tuple<>&) {}
	template<typename T, typename... Rest>
	void print_tuple(ostream& os, const tuple<T, Rest...>& t) {
		os << get<0>(t);
		if (sizeof...(Rest) > 0) {
			os << ",";
			print_tuple(os, reinterpret_cast<const tuple<Rest...>&>(t));
		}
	}
	template<typename... Args>
	ostream& operator<<(ostream& os, const tuple<Args...>& t) {
		os << "(";
		print_tuple(os, t);
		return os << ")";
	}
	template<typename T1, typename T2>
	istream &operator>>(istream &A, pair<T1, T2> &b) {
		return A >> b.first >> b.second;
	}
	template<typename T>
	void print_array(T b, T e, string s = " ") {
		while (b != e) {
			cout << *b;
			b++;
			if (b != e) {
				cout << s;
			}
		}
	}
	template<typename T>
	void auto_print(T &b, size_t n, string s = " ") {
		for (size_t i = 1; i < n; i++) {
			cout << b[i] << s;
		}
		cout << b[n];
	}
	template<typename T>
	void auto_print(T &b, string s = " ") {
		for (auto i : b) {
			cout << i << s;
		}
	}
	template<typename T>
	void print_n(T b, size_t n, string s = " ") {
		if (n == 0) return;
		cout << *b;
		for (size_t i = 1; i < n; i++) {
			b++;
			cout << s << *b;
		}
	}
	template<typename T>
	void read_array(T b, T e) {
		while (b != e) {
			cin >> *b;
			b++;
		}
	}
	template<typename T>
	void auto_read(T &b, size_t n) {
		for (size_t i = 1; i <= n; i++) {
			cin >> b[i];
		}
	}
	template<typename T>
	void read_n(T b, size_t n) {
		cin >> *b;
		for (size_t i = 1; i < n; i++) {
			b++;
			cin >> *b;
		}
	}
	template <typename T>
	std::string to_string(const T& value) {
		std::ostringstream oss;
		oss << value;
		return oss.str();
	}
	std::string debug_index() {
		return "";
	}
	template <typename first_t, typename... rest_t>
	std::string debug_index(const first_t& first, const rest_t&... rest) {
		return "[" + to_string(first) + "]" + debug_index(rest...);
	}
	template <typename T>
	auto get_value(T&& arr) -> decltype(std::forward<T>(arr)) {
		return std::forward<T>(arr);
	}
	template <typename T, typename first_t, typename... rest_t>
	auto get_value(T&& arr, first_t&& first, rest_t&&... rest) {
		return get_value(
			std::forward<T>(arr)[std::forward<first_t>(first)],
			std::forward<rest_t>(rest)...
		);
	}
	#define debug(first, ...) #first << debug_index(__VA_ARGS__) << " = " << get_value(first, ##__VA_ARGS__)
	#define spc << ' ' <<
	#undef quick_io_int_length_limit
	#undef quick_io_int_radix_type
	#undef quick_io_length_type
}
using namespace quick_io;
namespace MATH {
	template<typename Ta, typename Tb, typename Tm>
	Ta quickpower(Ta a, Tb b, Tm MOD) { // MOD \in P
		if (b < 0) {
			b = b % (MOD - 1) + MOD - 1;
		}
		a %= MOD;
		Ta c = 1;
		while (b) {
			if (b & 1) {
				c *= a;
				c %= MOD;
			}
			a *= a;
			a %= MOD;
			b >>= 1;
		}
		return c;
	}
	template<typename T>
	T gcd(T a, T b) {
		if (b == T(0))
			return a;
		return gcd(b, a % b);
	}
	template<typename T>
	T lcm(T a, T b) {
		return a * b / gcd(a, b);
	}
	template<typename T, typename T1, typename T2>
	T exgcd(T a, T b, T1 &x, T2 &y) {
		if (b == 0) {
			x = 1;
			y = 0;
			return a;
		}
		T ans = exgcd(b, a % b, x, y);
		T1 X = y;
		T2 Y = (T2)x - ((T2)a / (T2)b) * y;
		x = X;
		y = Y;
		return ans;
	}
	int log2_(char k) { return 31 - __builtin_clz((unsigned int)k); }
	int log2_(unsigned char k) { return 31 - __builtin_clz((unsigned int)k); }
	int log2_(short k) { return 31 - __builtin_clz((unsigned int)k); }
	int log2_(unsigned short k) { return 31 - __builtin_clz((unsigned int)k); }
	int log2_(int k) { return 31 - __builtin_clz((unsigned int)k); }
	int log2_(unsigned int k) { return 31 - __builtin_clz((unsigned int)k); }
	int log2_(long long k) { return 63 - __builtin_clzll((unsigned long long)k); }
	int log2_(unsigned long long k) { return 63 - __builtin_clzll((unsigned long long)k); }
	template<typename T, typename T2>
	void build_power(T *power_array, T2 power_base, size_t len) {
		power_array[0] = 1;
		for (size_t i = 1; i <= len; i++) {
			power_array[i] = power_array[i - 1] * (T)power_base;
		}
	}
	template<typename T1, typename T2>
	void build_factorial(int n, T1 *f, T2 *inv) {
		f[0] = 1;
		for (int i = 1; i <= n; i++) {
			f[i] = f[i - 1] * (T1)i;
		}
		if (inv == nullptr) {
			return;
		}
		inv[n] = T2(1) / T2(f[n]);
		for (int i = n - 1; i >= 0; i--) {
			inv[i] = inv[i + 1] * (T2)(i + 1);
		}
	}
	template<typename T1, typename T2>
	T1 C(size_t n, size_t m, T1 *f, T2 *i) {
		if (m > n) return 0;
		return f[n] * (T1)i[m] * (T1)i[n - m];
	}
}
namespace modulo_int {
	#define mint_int long long
	void exgcd(mint_int& x, mint_int& y, mint_int n, mint_int m) {
		if (m) {
			exgcd(y, x, m, n % m);
			y -= n / m * x;
		} else {
			x = 1;
			y = 0;
		}
	}
	mint_int mint_exgcd_a, mint_exgcd_b;
	#define mint_mod mod
	struct mint {
		mint_int n;
		mint() : n(0) {}
		mint(const mint_int &_n) { n = (_n % mint_mod + mint_mod) % mint_mod; }
		template<typename T> const mint operator+(const T &x) const { return n + mint(x).n; }
		template<typename T> const mint operator-(const T &x) const { return n - mint(x).n; }
		template<typename T> const mint operator*(const T &x) const { return n * mint(x).n; }
		template<typename T> const mint operator%(const T &x) const { return n % mint(x).n; }
		template<typename T> const mint operator|(const T &x) const { return n | mint(x).n; }
		template<typename T> const mint operator&(const T &x) const { return n & mint(x).n; }
		template<typename T> const mint operator^(const T &x) const { return n ^ mint(x).n; }
		template<typename T> const mint operator/(const T &x) const {
			exgcd(mint_exgcd_a, mint_exgcd_b, mint(x).n, mint_mod);
			return n * mint_exgcd_a;
		}
		template<typename T> mint &operator+=(const T x) { return *this = *this + (mint)x; }
		template<typename T> mint &operator-=(const T x) { return *this = *this - (mint)x; }
		template<typename T> mint &operator*=(const T x) { return *this = *this * (mint)x; }
		template<typename T> mint &operator/=(const T x) { return *this = *this / (mint)x; }
		template<typename T> mint &operator%=(const T x) { return *this = *this % (mint)x; }
		template<typename T> mint &operator|=(const T x) { return *this = *this | (mint)x; }
		template<typename T> mint &operator&=(const T x) { return *this = *this & (mint)x; }
		template<typename T> mint &operator^=(const T x) { return *this = *this ^ (mint)x; }
		mint &operator++() { return *this = n + 1; }
		mint &operator--() { return *this = n - 1; }
		mint operator++(signed) {
			n = ((n + 1 == mint_mod) ? 0 : (n + 1));
			return n - 1;
		}
		mint operator--(signed) {
			n = (n ? (n - 1) : (mint_mod - 1));
			return n + 1;
		}
		template<typename T> bool  operator<(const T &b) { return n <  mint(b).n; }
		template<typename T> bool operator<=(const T &b) { return n <= mint(b).n; }
		template<typename T> bool  operator>(const T &b) { return n >  mint(b).n; }
		template<typename T> bool operator>=(const T &b) { return n >= mint(b).n; }
		template<typename T> bool operator==(const T &b) { return n == mint(b).n; }
		template<typename T> bool operator!=(const T &b) { return n != mint(b).n; }
		operator mint_int() const { return n; }
		mint operator-() const { return -n; }
		const mint &operator+() const { return *this; }
	};
	istream &operator>>(istream &A, mint &b) {
		mint_int c;
		A >> c;
		b = c;
		return A;
	}
	ostream &operator<<(ostream &A, const mint &b) {
		return A << b.n;
	}
	#undef mint_mod
	#undef mint_int
}
namespace fast_ios {
	// #define fast_ios_buffer_enough
	// #define fast_is_buffer_enough
	// #define fast_os_buffer_enough
	// #define fast_ios_jump_invisible
	// #define fast_is_jump_invisible
	// #define fast_os_jump_invisible
	#ifdef fast_ios_buffer_enough
		#define fast_is_buffer_enough
		#define fast_os_buffer_enough
	#endif
	#ifdef fast_ios_jump_invisible
		#define fast_is_jump_invisible
		#define fast_os_jump_invisible
	#endif
	template<typename T>
	struct fast_make_unsigned : make_unsigned<T> {};
	template<>
	struct fast_make_unsigned<__int128> {
		typedef unsigned __int128 type;
	};
	template<>
	struct fast_make_unsigned<unsigned __int128> {
		typedef unsigned __int128 type;
	};
	template<size_t buffer_size = 65536>
	struct fast_reader_t {
		// short, int, long, long long, __int128
		// unsigned short, int, long, long long, __int128
		// very safe if there are no overflow
		size_t cursor;
		unsigned char c;
		unsigned char buffer[buffer_size];
		inline fast_reader_t() : cursor(buffer_size), c(EOF) {}
		inline unsigned char &get() {
			#ifndef fast_is_buffer_enough
			if (cursor < buffer_size) {
			#endif
				return c = buffer[cursor++];
			#ifndef fast_is_buffer_enough
			}
			for (size_t i = fread(buffer, 1, buffer_size, stdin); i < buffer_size; i++) {
				buffer[i] = EOF;
			}
			return c = buffer[(cursor = 0)++];
			#endif
		}
		inline void unget() {
			cursor--;
		}
		template<typename T>
		typename enable_if<(is_integral<T>::value
							&& is_unsigned<T>::value
							|| is_same<T, unsigned __int128>::value)
						&& !is_same<T, unsigned char>::value
						 , fast_reader_t&>::type
		inline operator>>(T &x) {
			x = 0;
			while (get() < '0' || c > '9');
			do {
				x = (x << 3) + (x << 1) + (c ^ '0');
			} while (get() >= '0' && c <= '9');
			#ifndef fast_is_jump_invisible
			unget();
			#endif
			return *this;
		}
		template<typename T>
		typename enable_if<(is_integral<T>::value
							&& is_signed<T>::value
							|| is_same<T, __int128>::value)
						&& !is_same<T, char>::value
						 , fast_reader_t&>::type
		inline operator>>(T &x) {
			typename fast_make_unsigned<T>::type x_ = 0;
			bool sign = false;
			while ((get() < '0' || c > '9') && c != '-' && c != '+');
			if (c == '-') {
				sign = true;
				get();
			} else if (c == '+') {
				get();
			}
			do {
				x_ = (x_ << 3) + (x_ << 1) + (c ^ '0');
			} while (get() >= '0' && c <= '9');
			if (sign && x_) {
				x = -T(x_ - 1) - 1;
			} else {
				x = T(x_);
			}
			#ifndef fast_is_jump_invisible
			unget();
			#endif
			return *this;
		}
		inline fast_reader_t &operator>>(char &x) {
			while (!isgraph(get()));
			x = c;
			return *this;
		}
		inline fast_reader_t &operator>>(unsigned char &x) {
			while (!isgraph(get()));
			x = c;
			return *this;
		}
		inline fast_reader_t &operator>>(string &x) {
			x = "";
			while (get() <= 32);
			do {
				x += c;
			} while (get() > 32);
			#ifndef fast_is_jump_invisible
			unget();
			#endif
			return *this;
		}
		inline fast_reader_t &operator>>(char *x) {
			while (get() <= 32);
			do {
				*(x++) = c;
			} while (get() > 32);
			*x = 0;
			#ifndef fast_is_jump_invisible
			unget();
			#endif
			return *this;
		}
		template<typename T>
		typename enable_if<is_floating_point<T>::value, fast_reader_t&>::type
		inline operator>>(T &x) {
			x = 0;
			bool sign = false;
			while ((get() < '0' || c > '9') && c != '-' && c != '+' && c != '.');
			if (c == '-') {
				sign = true;
				get();
			} else if (c == '+') {
				get();
			} else if (c == '.') {
				unget();
			}
			if (c != '.') do {
				x = x * 10 + (c ^ '0');
			} while (get() >= '0' && c <= '9');
			if (c == '.') {
				T f = 0.1;
				while (get() >= '0' && c <= '9') {
					x += (c ^ '0') * f;
					f /= 10;
				}
			}
			if (sign) {
				x = -x;
			}
			unget();
			return *this;
		}
	};
	template<size_t buffer_size = 65536>
	struct fast_writer_t {
		// short, int, long, long long, __int128
		// unsigned short, int, long, long long, __int128
		size_t cursor;
		unsigned char buffer[buffer_size];
		inline fast_writer_t() : cursor(0) {}
		inline ~fast_writer_t() {
			if (cursor) {
				flush();
			}
		}
		inline void flush() {
			__builtin_fwrite(buffer, 1, cursor, stdout);
			cursor = 0;
		}
		inline void put(unsigned char c) {
			buffer[cursor++] = c;
			#ifndef fast_os_buffer_enough
			if (cursor == buffer_size) {
				flush();
			}
			#endif
		}
		template<typename T>
		typename enable_if<(is_integral<T>::value
							&& is_unsigned<T>::value
							|| is_same<T, unsigned __int128>::value)
						&& !is_same<unsigned char, T>::value,
						fast_writer_t&>::type
		inline operator<<(const T &x) {
			if (x >= T(10)) {
				*this << x / T(10);
			}
			put('0' ^ x % T(10));
			return *this;
		}
		template<typename T>
		typename enable_if<(is_integral<T>::value
							&& is_signed<T>::value
							|| is_same<T, __int128>::value)
						&& !is_same<char, T>::value,
						fast_writer_t&>::type
		inline operator<<(const T &x) {
			typename fast_make_unsigned<T>::type x_ = x;
			if (x < T(0)) {
				put('-');
				x_ = 0 - x_;
			}
			return *this << x_;
		}
		inline fast_writer_t &operator<<(char x) {
			put(x);
			return *this;
		}
		inline fast_writer_t &operator<<(unsigned char x) {
			put(x);
			return *this;
		}
		inline fast_writer_t &operator<<(const string &x) {
			for (string::const_iterator it = x.cbegin(); it != x.cend(); it++) {
				put(*it);
			}
			return *this;
		}
		inline fast_writer_t &operator<<(const char *x) {
			while (*x) {
				put(*(x++));
			}
			return *this;
		}
		inline fast_writer_t &operator<<(const unsigned char *x) {
			while (*x) {
				put(*(x++));
			}
			return *this;
		}
	};
	fast_reader_t<> ewin;
	fast_writer_t<> ewout;
}
#define __USING__SAFE_FOR_LOOP__ 1
#define __USING__PSEUDO_CODE_EXTEND__OF__FOR_LOOP__
namespace __pseudo_code_extend {
	namespace __for_loop {
		namespace safe { // safe for only to mod
			struct fft_translator {};
			struct ffdt_translator {};
			template<typename T>
			struct fft_range {
				struct iterator {
					T x;
					bool e;
					const fft_range *base;
					const T &operator*() const { return x; }
					bool operator!=(const iterator &b) const { return x != b.x || e != b.e; }
					iterator &operator++() {
						if (x == base->e) e = true;
						else ++x;
						return *this;
					}
				};
				T b, e;
				iterator begin() const { return {b, false, this}; }
				iterator end() const { return {e, true, this}; }
			};
			template<typename T2, typename T>
			fft_range<T2> operator,(fft_range<T2> ans, T &&e) {
				ans.e = e;
				return ans;
			}
			template<typename T>
			fft_range<std::decay_t<T> > operator,(T &&b, fft_translator) {
				fft_range<std::decay_t<T> > ans;
				ans.b = b;
				return ans;
			}
			template<typename T>
			struct ffdt_range {
				struct iterator {
					T x;
					bool e;
					const ffdt_range *base;
					const T &operator*() const { return x; }
					bool operator!=(const iterator &b) const { return x != b.x || e != b.e; }
					iterator &operator++() {
						if (x == base->e) e = true;
						else --x;
						return *this;
					}
				};
				T b, e;
				iterator begin() const { return {b, false, this}; }
				iterator end() const { return {e, true, this}; }
			};
			template<typename T2, typename T>
			ffdt_range<std::decay_t<T2> > operator,(ffdt_range<T2> ans, T &&e) {
				ans.e = e;
				return ans;
			}
			template<typename T>
			ffdt_range<std::decay_t<T> > operator,(T &&b, ffdt_translator) {
				ffdt_range<std::decay_t<T> > ans;
				ans.b = b;
				return ans;
			}
		}
		namespace fast {
			struct fft_translator {};
			struct ffu_translator {};
			struct ffdt_translator {};
			struct ffdu_translator {};
			template<typename T>
			struct fft_range {
				struct iterator {
					T x;
					const T &operator*() const { return x; }
					bool operator!=(const iterator &b) const { return x != b.x; }
					iterator &operator++() { ++x; return *this; }
				};
				T b, e;
				iterator begin() const { return {b}; }
				iterator end() const { return {e}; }
			};
			template<typename T>
			struct ffu_range_begin { T b; };
			template<typename T2, typename T>
			fft_range<T2> operator,(fft_range<T2> ans, T &&e) {
				++(ans.e = e);
				return ans;
			}
			template<typename T>
			fft_range<std::decay_t<T> > operator,(T &&b, fft_translator) {
				fft_range<std::decay_t<T> > ans;
				ans.b = b;
				return ans;
			}
			template<typename T2, typename T>
			fft_range<T2> operator,(ffu_range_begin<T2> ans_u, T &&e) {
				fft_range<T2> ans;
				ans.b = ans_u.b;
				ans.e = e;
				return ans;
			}
			template<typename T>
			ffu_range_begin<std::decay_t<T> > operator,(T &&b, ffu_translator) {
				return {b};
			}
			template<typename T>
			struct ffdt_range {
				struct iterator {
					T x;
					const T &operator*() const { return x; }
					bool operator!=(const iterator &b) const { return x != b.x; }
					iterator &operator++() { --x; return *this; }
				};
				T b, e;
				iterator begin() const { return {b}; }
				iterator end() const { return {e}; }
			};
			template<typename T>
			struct ffdu_range_begin { T b; };
			template<typename T2, typename T>
			ffdt_range<T2> operator,(ffdt_range<T2> ans, T &&e) {
				--(ans.e = e);
				return ans;
			}
			template<typename T>
			ffdt_range<std::decay_t<T> > operator,(T &&b, ffdt_translator) {
				ffdt_range<std::decay_t<T> > ans;
				ans.b = b;
				return ans;
			}
			template<typename T2, typename T>
			ffdt_range<T2> operator,(ffdu_range_begin<T2> ans_u, T e) {
				ffdt_range<T2> ans;
				ans.b = ans_u.b;
				ans.e = e;
				return ans;
			}
			template<typename T>
			ffdu_range_begin<std::decay_t<T> > operator,(T &&b, ffdu_translator) {
				return {b};
			}
		}
	}
}
#ifdef __USING__PSEUDO_CODE_EXTEND__OF__FOR_LOOP__
#if __USING__SAFE_FOR_LOOP__
#define to , __pseudo_code_extend::__for_loop::safe::fft_translator() ,
#define up_to to
#define down_to , __pseudo_code_extend::__for_loop::safe::ffdt_translator() ,
#else
#define to , __pseudo_code_extend::__for_loop::fast::fft_translator() ,
#define up_to to
#define down_to , __pseudo_code_extend::__for_loop::fast::ffdt_translator() ,
#endif
#define until , __pseudo_code_extend::__for_loop::fast::ffu_translator() ,
#define up_until until
#define down_until , __pseudo_code_extend::__for_loop::fast::ffdu_translator() ,
#define to_safe , __pseudo_code_extend::__for_loop::safe::fft_translator() ,
#define until_safe , __pseudo_code_extend::__for_loop::fast::ffu_translator() ,
#define up_to_safe to_safe
#define up_until_safe until_safe
#define down_to_safe , __pseudo_code_extend::__for_loop::safe::ffdt_translator() ,
#define down_until_safe , __pseudo_code_extend::__for_loop::fast::ffdu_translator() ,
#define to_fast , __pseudo_code_extend::__for_loop::fast::fft_translator() ,
#define until_fast , __pseudo_code_extend::__for_loop::fast::ffu_translator() ,
#define up_to_fast to_fast
#define up_until_fast until_fast
#define down_to_fast , __pseudo_code_extend::__for_loop::fast::ffdt_translator() ,
#define down_until_fast , __pseudo_code_extend::__for_loop::fast::ffdu_translator() ,
#endif
template<typename T_key,
		 typename T_value,
		 typename head_container = vector<size_t>,
		 typename nxt_container = vector<size_t>,
		 typename data_container = vector<T_value>,
		 typename index_type = size_t>
struct basic_fs {
	// front star, without initialization
	data_container data;
	nxt_container nxt;
	head_container head;
	index_type cnt;
	basic_fs() : cnt(0) {}
	struct data_t {
		T_key key;
		basic_fs* base;
		struct iterator {
			index_type pos;
			data_t* base;
			T_value &operator*() { return base->base->data[pos]; }
			iterator &operator++() { pos = base->base->nxt[pos]; return *this; }
			operator index_type&() { return pos; }
		};
		iterator end() { return {0, this}; }
		iterator begin() { return {base->head[key], this}; }
		void push_back(const T_value &value) {
			base->data[++base->cnt] = value;
			base->nxt[base->cnt] = base->head[key];
			base->head[key] = base->cnt;
		}
		bool empty() { return base->head[key] == 0; }
		size_t size() {
			size_t ans = 0;
			for (size_t i = base->head[key]; i; i = base->nxt[i]) {
				ans++;
			}
			return ans;
		}
		void clear() { base->head[key] = 0; }
		friend ostream &operator<<(ostream &os, const data_t &a) {
			os << "[";
			size_t i = a.base->head[a.key];
			while (i) {
				os << a.base->data[i];
				i = a.base->nxt[i];
				if (i) {
					os << ",";
				}
			}
			return os << "]";
		}
	};
	data_t operator[](const T_key &x) { return {x, this}; }
};
template<typename T,
		 size_t index_range,
		 size_t value_size = index_range>
using array_fs = basic_fs<size_t,
						  T,
						  int[index_range],
						  int[value_size],
						  T[value_size],
						  int>;
namespace graph_algorithm {
	// directivity "d"/"u", weightiness "w"/"u"
	template<typename T, typename is_t>
	void read_graph_d_u(T &&e, int m, is_t &is) {
		int u, v;
		while (m--) {
			is >> u >> v;
			e[u].push_back(v);
		}
	}
	template<typename T, typename is_t>
	void read_graph_d_w(T &&e, int m, is_t &is) {
		int u, v, w;
		while (m--) {
			is >> u >> v >> w;
			e[u].push_back({v, w});
		}
	}
	template<typename T, typename is_t>
	void read_graph_u_u(T &&e, int m, is_t &is) {
		int u, v;
		while (m--) {
			is >> u >> v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
	}
	template<typename T, typename is_t>
	void read_graph_u_w(T &&e, int m, is_t &is) {
		int u, v, w;
		while (m--) {
			is >> u >> v >> w;
			e[u].push_back({v, w});
			e[v].push_back({u, w});
		}
	}
	template<typename T>
	void read_graph_d_u(T &&e, int m) {
		read_graph_d_u(e, m, cin);
	}
	template<typename T>
	void read_graph_d_w(T &&e, int m) {
		read_graph_d_w(e, m, cin);
	}
	template<typename T>
	void read_graph_u_u(T &&e, int m) {
		read_graph_u_u(e, m, cin);
	}
	template<typename T>
	void read_graph_u_w(T &&e, int m) {
		read_graph_u_w(e, m, cin);
	}
}
namespace my_random {
	std::chrono::high_resolution_clock::duration::rep time_nano() {
		return std::chrono::high_resolution_clock::now().time_since_epoch().count();
	}
	template<typename T = unsigned long long>
	struct xorshift {
		T seed;
		unsigned char a, b, c;
		xorshift(const T &_seed,
				 unsigned char _a = 5,
				 unsigned char _b = 11,
				 unsigned char _c = 54)
			: seed(_seed),
			  a(_a),
			  b(_b),
			  c(_c) {
			operator()();
			operator()();
			operator()();
			operator()();
		}
		xorshift(T &&_seed = time_nano(),
				 unsigned char _a = 5,
				 unsigned char _b = 11,
				 unsigned char _c = 54)
			: seed(_seed),
			  a(_a),
			  b(_b),
			  c(_c) {
			operator()();
			operator()();
			operator()();
			operator()();
		}
		const T &operator()() {
			return seed ^= (seed ^= (seed ^= seed << a) >> b) << c;
		}
	};
}
#define lowbit(x) ((x)&-(x))
template<typename T, typename BIT_index = size_t, typename container = vector<T> >
struct BIT {
	container t;
	BIT() {}
	BIT(const BIT_index &n) : t(n, 0) {}
	BIT(T *a, const size_t &n) : t(a, next(a, n)) {
		for (BIT_index i = 1; i < n; i++) {
			if (i + lowbit(i) < n) {
				t[i + lowbit(i)] += t[i];
			}
		}
	}
	template<typename ite>
	BIT(const ite &b, const ite &e) : t(b, e) {
		BIT_index n = t.size();
		for (BIT_index i = 1; i < n; i++) {
			if (i + lowbit(i) < n) {
				t[i + lowbit(i)] += t[i];
			}
		}
	}
	BIT(const BIT_index &n, const T &a) : t(n, a) {
		for (BIT_index i = 1; i < n; i++) {
			if (i + lowbit(i) < n) {
				t[i + lowbit(i)] += t[i];
			}
		}
	}
	void clear(const BIT_index &len = 0) {
		t = container(len, 0);
	}
	size_t size() {
		return t.size();
	}
	void update(BIT_index x, const T k) {
		if (x == 0) {
			t[0] += k;
		}
		#ifndef BIT_limit
			#define __BIT_hd_limit(x) (x < t.size())
		#else
			#define __BIT_hd_limit(x) (BIT_limit(x))
		#endif
		while (x != 0 && __BIT_hd_limit(x)) {
			t[x] += k;
			x += lowbit(x);
		}
		#undef __BIT_hd_limit
	}
	T query(BIT_index x) {
		T ans = t[0];
		while (x) {
			ans += t[x];
			x ^= lowbit(x);
		}
		return ans;
	}
	T query(const BIT_index l, const BIT_index r) {
		return query(r) - (l ? query(l - 1) : T(0));
	}
	T operator[](const BIT_index b) {
		return query(b, b);
	}
	void resize(const BIT_index n) {
		BIT_index m = t.size();
		if (n <= t.size()) {
			t.erase(t.begin() + n, t.end());
			return;
		}
		t.insert(t.end(), n - m, 0);
		for (BIT_index i = 0; i < n; i++) {
			if (i + lowbit(i) >= m && i + lowbit(i) < n) {
				t[i + lowbit(i)] += t[i];
			}
		}
	}
};
#undef lowbit
template<typename T>
typename decay<decltype(*declval<T>())>::type range_sum(T a, const T &b) {
	if (a == b) return *T();
	typename decay<decltype(*declval<T>())>::type ans = *(a++);
	while (a != b) {
		ans += *(a++);
	}
	return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_prod(T a, const T &b) {
	if (a == b) return *T();
	typename decay<decltype(*declval<T>())>::type ans = *(a++);
	while (a != b) {
		ans *= *(a++);
	}
	return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_bor(T a, const T &b) {
	if (a == b) return *T();
	typename decay<decltype(*declval<T>())>::type ans = *(a++);
	while (a != b) {
		ans |= *(a++);
	}
	return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_band(T a, const T &b) {
	if (a == b) return *T();
	typename decay<decltype(*declval<T>())>::type ans = *(a++);
	while (a != b) {
		ans &= *(a++);
	}
	return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_bxor(T a, const T &b) {
	if (a == b) return *T();
	typename decay<decltype(*declval<T>())>::type ans = *(a++);
	while (a != b) {
		ans ^= *(a++);
	}
	return ans;
}
template<typename T, typename T2>
void range_plus(T a, const T &b, const T2 &c) { while (a != b) { *a += c; a++; } }
template<typename T, typename T2>
void range_minus(T a, const T &b, const T2 &c) { while (a != b) { *a -= c; a++; } }
template<typename T, typename T2>
void range_multiplies(T a, const T &b, const T2 &c) { while (a != b) { *a *= c; a++; } }
template<typename T, typename T2>
void range_divides(T a, const T &b, const T2 &c) { while (a != b) { *a /= c; a++; } }
template<typename T, typename T2>
void range_negate(T a, const T &b) { while (a != b) { *a = -*a; a++; } }
template<typename T, typename T2>
void range_band(T a, const T &b, const T2 &c) { while (a != b) { *a &= c; a++; } }
template<typename T, typename T2>
void range_bor(T a, const T &b, const T2 &c) { while (a != b) { *a |= c; a++; } }
template<typename T, typename T2>
void range_bxor(T a, const T &b, const T2 &c) { while (a != b) { *a ^= c; a++; } }
template<typename T, typename T2>
void range_bnot(T a, const T &b) { while (a != b) { *a = ~*a; a++; } }
template<typename T1, typename T2>
typename decay<typename common_type<T1, T2>::type>::type std_max(const T1 &a, const T2 &b) { return a > b ? a : b; }
template<typename T1, typename T2>
typename decay<typename common_type<T1, T2>::type>::type std_min(const T1 &a, const T2 &b) { return a < b ? a : b; }
template<typename T>
void std_swap(T &x, T &y) { swap(x, y); }
template<typename T1, typename T2>
T1 &ckmin(T1 &a, const T2 &b) { if (b < a) { a = b; } return a; }
template<typename T1, typename T2>
T1 &ckmax(T1 &a, const T2 &b) { if (b > a) { a = b; } return a; }
template<typename T> // const reference to reference
T &crtr(const T& x) { return (T&)x; }
void sios() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
#define int long long
#if 1
using ll = long long;
using ull = unsigned long long;
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
using sti = set<int>;
using mpii = map<int, int>;
using usti = unordered_set<int>;
using umpii = unordered_map<int, int>;
using msti = multiset<int>;
using umsti = unordered_multiset<int>;
using sos = ostream;
using sis = istream;
using soss = ostringstream;
using siss = istringstream;
#endif
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define mmin(x, y) ((x) < (y) ? (x) : (y))
#define mmax(x, y) ((x) > (y) ? (x) : (y))
#define Cpre(x) mint fac[(x) + 5], inv[(x) + 5]; struct Cpre##x##_t { Cpre##x##_t() { build_factorial(x, fac, inv); } } Cpre##x;
#define lowbit(x) ((x) & -(x))
#define abs(x) ((x) < 0 ? -(x) : (x))
// #define swap(a,b) a ^= b ^= a ^= b
#define INF 1e18
#define bin(a,b) bitset<a>(b)
#define getbit(a, b) (((a) >> (b)) & 1)
#define cde(...) cout << debug(__VA_ARGS__) << endl
#define dmi << '-' <<
#define dpl << '+' <<
#define dmu << '*' <<
#define ddi << '/' <<
#define dor << '|' <<
#define dan << '&' <<
#define dxo << '^' <<
#define dno << '!' <<
#define dco << ',' <<
#define ddo << '.' <<
#define mpow auto_quickpower<mint>
ostream &cans(cout);
// #define cout cerr
using namespace MATH;
using modulo_int::mint;
using namespace graph_algorithm;
using namespace my_random;
using fast_ios::ewin;
using fast_ios::ewout;
// #define cin ewin
// #define cout ewout
#define MAXN 2505
int n, c[MAXN], v[MAXN], dp[MAXN][MAXN], ans[MAXN];
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> v[i];
	}
	memset(dp, -63, sizeof(dp));
	memset(ans, -63, sizeof(ans));
	dp[0][0] = 0;
	for (int i = n; i >= 1; i--) {
		if (!c[i]) continue;
		// cout << i << ":\n";
		for (int j = 0; j <= n / i; j++) {
			for (int k = 0; k <= n; k++) {
				if (!(j == 0 || k < i)) continue;
				deque<pair<int, int> > q;
				for (int pj = j, pk = k; pj <= n / i && pk <= n; pj++, pk += i) {
					while (!q.empty() && q.back().second < dp[pj][pk] - pj * v[i]) q.pop_back();
					q.push_back({pj, dp[pj][pk] - pj * v[i]});
					while (q.front().first + c[i] < pj) q.pop_front();
					dp[pj][pk] = q.front().second + pj * v[i];
					ckmax(ans[pj], dp[pj][pk]);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}