#if 1
//#define _CRT_SECURE_NO_WARNINGS		//scanf
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <set>
#include <map>
#include <numeric>
#include <cassert>
#include <iomanip>
#include <queue>
#include <chrono>
#define _SCL_SECURE_NO_WARNINGS
#include "boost/multiprecision/cpp_int.hpp"

#pragma warning (disable:4244)


using namespace std;

using int128 = boost::multiprecision::int128_t;
using int256 = boost::multiprecision::int256_t;
#if 0
#define int boost::multiprecision::int128_t
#else
#define int long long
#endif
#if 1
constexpr long long MOD = 1000000007LL;
#else
constexpr long long MOD = 998244353LL;
#endif
constexpr long long INF = 1145141919810893LL;

//
#if 1


struct Val {
	int x = 0;
	int r = 0;
};

int count111 = 0;


//ダイクストラ法を使うときはTとしてこれを継承したものを使う
struct Dijk {
	static constexpr auto MAXVAL = std::numeric_limits<int>::max();
	int prev = -1;		//最短経路をたどる際の前の頂点
	int dis = MAXVAL;
};
struct Bellman {
	int dis = std::numeric_limits<int>::max() / 2;				//緩和の初期値(何かが足されてもオーバーフローしないように)
	int predecessor = -1;										//直前の頂点？
};
struct Edge {
	int next;
	int w = 1;
};
template<class T>
struct Vertex {
	std::vector<Edge>edges;
	T val;
};
template<class T>
struct Graph {
	std::vector<Vertex<T>> vertex;
public:
	Graph(size_t nVertex = 0) :vertex(nVertex) {
	}
	void setArray(int u, int v, int w = 1) {
		vertex[u].edges.push_back(Edge{ v ,w });
	}
	void setConnect(int u, int v, int w = 1) {
		setArray(u, v, w);
		setArray(v, u, w);
	}
	T& val(int u) {
		return vertex[u].val;
	}
	void dfsImpl(int pos, int prev, std::function<bool(int now, int next, int w)> func) {
		count111 += val(pos).x;
		val(pos).r = count111;
		for (auto& e : vertex[pos].edges) {
			if (e.next == prev) continue;
			if (func(pos, e.next, e.w)) {
				dfsImpl(e.next, pos, func);
			}
			//ここに追加する場合も
		}
		count111 -= vertex[pos].val.x;
	}
	void dfsCustom(int pos, int prev);
	//深さ優先探索
	void dfs(int pos, std::function<bool(int now, int next, int w)> func) {
		dfsImpl(pos, -1, func);
	}
	//幅優先探索
	void bfs(int pos, std::function<bool(int now, int next, int w)> func) {
		std::unordered_set<int> set;
		set.insert(pos);
		while (!set.empty()) {
			std::unordered_set<int> setNew;
			for (auto& one : set) {
				for (auto& e : vertex[one].edges) {
					if (func(one, e.next, e.w)) {
						setNew.insert(e.next);
					}
				}
			}
			set = setNew;
		}
	}
	//posStartを始点とするダイクストラ法
	//木						:O(V)	※動作確認済
	//有向非巡回グラフ(DAG)		:O(V^2)
	//ループ有					:O(V^2)	※未検証
	//ループ有(負の閉路)		:ダイクストラは適用外
	void dijkstraOLD(int posStart) {
		val(posStart).dis = 0;
		//
		bfs(posStart, [&](int now, int next, int w) {
			if (val(next).dis > val(now).dis + w) {
				val(next).dis = val(now).dis + w;
				return true;
			}
			return false;
			});
	}
	//木						:O(V)			※負の重みがあっても多分平気(未検証)
	//有向非巡回グラフ(DAG)		:O(E+VlogV)		※負の重みがあるとO(V^2)(未検証)
	//ループ有					:O(E+VlogV)
	//ループ有(負の閉路)		:ダイクストラは適用外
	struct VertexTmp {
		int ver;
		int prev;	//直前の頂点
	};
	void dijkstra(int posStart) {
		val(posStart).dis = 0;
		std::multimap<int, VertexTmp>q;		//累計距離->頂点
		const int N = vertex.size();
		for (auto& edge : vertex[posStart].edges) {
			q.insert({ edge.w + val(posStart).dis ,VertexTmp{edge.next,posStart} });
		}
		val(posStart).dis = INF;			//始点までの距離はループして初めに戻ってくるのにする
		while (!q.empty()) {
			auto itr = q.begin();
			if (val(itr->second.ver).dis > itr->first) {
				val(itr->second.ver).dis = itr->first;
				val(itr->second.ver).prev = itr->second.prev;
				for (auto& edge : vertex[itr->second.ver].edges) {
					q.insert({ edge.w + val(itr->second.ver).dis ,VertexTmp{edge.next,itr->second.ver} });
				}
			}
			q.erase(itr);
		}
	}
	//posStartを始点とするベルマン-フォード法
	//負の閉路に対応するがO(VE)
	//負の経路を検出したらfalseを返す(この場合、結果が正しいとは限らない)
	//posEndを指定した場合、posStart -> posEnd　の最短経路間でのみ負経路検出を行う、-1なら全体
	bool bellmanFord(int posStart, int posEnd = -1) {
		// この実装では、グラフを頂点のリストと辺のリストで表す。
		// そして、各頂点の distance と predecessor 属性が
		// 最短経路を格納するよう変更していく。
		// Step 1: グラフの初期化
		val(posStart).dis = 0;
		// Step 2: 辺の緩和を反復
		for (int jj = 0; jj < vertex.size() * 2; ++jj) {
			for (int i = 0; i < vertex.size(); ++i) {
				for (auto& edge : vertex[i].edges) {
					auto tmp = val(i).dis + edge.w;
					if (val(edge.next).dis > tmp) {
						val(edge.next).dis = tmp;
						val(edge.next).predecessor = i;
					}
				}
			}
		}
		// Step 3: 負の重みの閉路がないかチェック
		if (0 > posEnd) {
			for (int i = 0; i < vertex.size(); ++i) {
				for (auto& edge : vertex[i].edges) {
					if (val(edge.next).dis > val(i).dis + edge.w) {
						return false;
					}
				}
			}
		}
		else {
			assert(false);	//なんかうまくできてないっぽい
			int v = posEnd;
			do {
				auto prev = val(v).predecessor;
				assert(prev != -1);
				int weight = std::numeric_limits<int>::min();
				for (auto& edge : vertex[prev].edges) {
					if (edge.next == v) {
						weight = edge.w;
						break;
					}
				}
				assert(weight != std::numeric_limits<int>::min());
				if (val(v).dis > val(prev).dis + weight) {
					return false;
				}
				v = prev;
			} while (v != posStart);
		}
		return true;
	}
	//DAGに対してトポロジカルソートを行う(O(V+E))
	//DAGではない場合は例外を投げる
	std::vector<int> topologicalSort() const {
		const int N = vertex.size();
		std::vector<int>ref(N);		//各ノードに向いている入力辺の数
		for (int i = 0; i < N; ++i) {
			for (auto& edge : vertex[i].edges) {
				ref[edge.next]++;
			}
		}
		//
		unordered_set<int> S;		//入力辺を持たないすべてのノードの集合
		std::vector<int>L;			//トポロジカルソートした結果を蓄積する空リスト
		L.reserve(N);
		for (int i = 0; i < N; ++i) {
			if (ref[i] == 0)S.insert(i);
		}
		while (!S.empty()) {
			auto itr = S.begin();
			int n = *itr;
			S.erase(itr);
			L.push_back(n);
			for (auto& edge : vertex[n].edges) {
				ref[edge.next]--;
				if (ref[edge.next] == 0) {
					S.insert(edge.next);
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			if (ref[i] != 0) {
				throw "DAGではない";
			}
		}
		return L;
	}
	//
	pair<int, int> radiusImpl(int pos) {
		int farestID = -1;
		int far = -1;
		val(pos) = 0;
		//dfsで正しい？？
		dfs(pos, [&](int now, int next, int w) ->bool {
			val(next) = 1 + val(now);
			if (val(next) > far) {
				far = val(next);
				farestID = next;
			}
			return true;
			});
		return { farestID, far };
	}
	//木の直径(O(V+E))
	//ループがある(木ではない)ときは間違った答えを返す(そもそも、O(V^3)未満で近似なしで解く方法が見つかってない)
	int radius() {
		if (vertex.size() <= 1)return 0;
		auto res = radiusImpl(0);
		res = radiusImpl(res.first);
		return res.second;
	}
	//隣接表現を行列表現に変換したうえでwfを行う(O(V^3))
	//有向グラフであっても動作
	std::vector<std::vector<int>> warshallFloyd() {
		const int N = vertex.size();
		std::vector<std::vector<int>> res(vertex.size());
		for (int i = 0; i < N; ++i) {
			res[i].resize(N);
			for (int j = 0; j < N; ++j) {
				res[i][j] = INF;
			}
		}
		for (int i = 0; i < N; ++i) {
			for (auto& e : vertex[i].edges) {
				res[i][e.next] = e.w;
			}
		}
		for (int k = 0; k < N; k++) {       // 経由する頂点
			for (int i = 0; i < N; i++) {    // 始点
				for (int j = 0; j < N; j++) {  // 終点
					res[i][j] = min(res[i][j], res[i][k] + res[k][j]);
				}
			}
		}
		return res;
	}
	//二部グラフであるかの判定(O(V+E)？)
	//二部グラフの場合は白い頂点のid配列を返す
	//二部グラフじゃない場合は空
	std::vector<int> bipartiteGraph() {
		std::vector<int>res;
		const int N = vertex.size();
		std::vector<int> color(N, -1);
		function<bool(int, int, int)> dfs = [&](int u, int prev, int c) {
			color[u] = c;
			if (c == 1) {
				res.push_back(u);
			}
			for (auto& edge : vertex[u].edges) {
				int v = edge.next;
				if (v == prev)continue;
				if (color[v] == -1) {
					if (!dfs(v, u, 1 - c)) return false;
				}
				else if (color[v] != 1 - c) {
					return false;
				}
			}
			return true;
		};
		if (!dfs(0, -1, 0)) return {};
		return res;
	}
};
#endif

//////////////////////////////////
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int sign(int x) {
	if (x > 0)return 1;
	if (x < 0)return -1;
	return 0;
}
//マイナスでも動作するmod(いちいち手で書くとunsignedの引き算オーバーフローで死にやすい)
int mod(int n, int m = MOD) {
	assert(0 < m);	//さすがに割る数は正でないといけない
	return (n % m + m) % m;
}
unsigned int mod(unsigned int n, unsigned int m = MOD) {
	assert(0 < m);	//さすがに割る数は正でないといけない
	return (n % m + m) % m;
}

//約数
std::vector<int> divisor(int n) {
	std::vector<int> ret;
	for (int i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) {
				ret.push_back(n / i);
			}
		}
	}
	return ret;
}

//素数判定
bool isPrime(int n) {
	if (n <= 1)return false;
	if (n == 2)return true;
	if (n % 2 == 0)return false;
	for (int i = 3; i * i <= n; i += 2) {
		if (n % i == 0)return false;
	}
	return true;
}

//素因数分解
std::map<int, int> primeFactorization(int n) {
	std::map<int, int> res;
	int k = 2;
	while (k * k <= n) {
		while (n % k == 0) {
			res[k]++;
			n /= k;
		}
		++k;
	}
	if (n != 1) {
		res[n]++;
	}
	return res;
}



//二項係数(N<=10^6,O(NlogN))、int128は使わなく64で十分
class Combination {
	std::vector<long long>fac, finv, inv;
	long long M;		//剰余
public:
	Combination(long long N, long long M_ = MOD)
		:fac(N + 1), finv(N + 1), inv(N + 1), M(M_) {
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for (long long i = 2; i < N + 1; i++) {
			fac[i] = fac[i - 1] * i % M;
			inv[i] = M - inv[M % i] * (M / i) % M;
			finv[i] = finv[i - 1] * inv[i] % M;
		}
	}
	long long get(long long n, long long k) {
		if (n < k) return 0;
		if (n < 0 || k < 0) return 0;
		return fac[n] * (finv[k] * finv[n - k] % M) % M;
	}
	long long factrial(int n) {
		return fac[n];
	}
};

//二項係数(N<=50,O(N^2))、剰余を取らないパターンはこっちで計算必須
class CombinationSmall {
	std::vector<std::vector<int>>com;
	CombinationSmall() :com(51) {
		for (int i = 0; i < com.size(); ++i) {
			com[i].resize(i + 1);
			for (int j = 0; j < i + 1; ++j) {
				if (j == 0 || i == j) {
					com[i][j] = 1;
				}
				else {
					com[i][j] = com[i - 1][j] + com[i - 1][j - 1];
				}
			}
		}
	}
public:
	long long get(int n, int k) {
		return com[n][k];
	}

};//CombinationSmall



#if 1

//Mを法とする逆数、計算量:？
int modInv(int a, int M = MOD) {
	int b = M, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}

template <class T>
void modify(T& n, T mod = MOD) {
	if (n < 0) {
		n %= mod;
		n += mod;
	}
	n %= mod;
}


void chmax(int& val, int max) {
	val = std::max({ val,max });
}

void chmax(double& val, double max) {
	val = std::max({ val,max });
}

void chmin(int& val, int min) {
	val = std::min({ val,min });
}
void chmin(double& val, double min) {
	val = std::min({ val,min });
}


#endif

//文字列の置き換え(遅い？)
int replace(std::string* str, const std::string& old_, const std::string& new_) {
	std::string& String1 = *str;
	//String1.reserve(str->size() * new_.size() / old_.size() + 1);
	std::string::size_type  Pos(String1.find(old_));
	int result = 0;
	while (Pos != std::string::npos) {
		result++;
		String1.replace(Pos, old_.length(), new_);
		Pos = String1.find(old_, Pos + new_.length());
	}
	return result;
}

#define ALL(t) t.begin(), t.end()


//LIS(最長増加部分列)
//eq = falseで狭義増加(1,3,7,9...)
//eq = trueで広義増加(1,1,3,7,7,7,7,9...)
std::vector<int> lis(const std::vector<int>& ary, bool eq = false) {
	std::vector<int>dp(ary.size());
	constexpr int intMax = std::numeric_limits<int>::max();
	fill(ALL(dp), intMax);
	for (int i = 0; i < ary.size(); ++i) {
		auto itr = std::lower_bound(ALL(dp), ary[i] + (eq ? 1 : 0));
		*itr = ary[i];
	}
	auto itr = std::lower_bound(ALL(dp), intMax);
	dp.resize(itr - dp.begin());
	return dp;
}

//座標圧縮:O(NlogN)
struct Compressor {
	std::set<int> buf;
	std::unordered_map<int, int>res;
public:
	template <class... Args>
	void insert(Args... args) {
		buf.insert(args...);
	}
	void calc() {
		res.clear();
		int i = 0;
		for (auto& one : buf) {
			res[one] = i;
			++i;
		}
	}
	int get(int n) const {
		return res.at(n);
	}
	std::vector<int> get(const std::vector<int>& v) const {
		std::vector<int> res(v.size());
		for (int i = 0; i < v.size(); ++i) {
			res[i] = get(v[i]);
		}
		return res;
	}
};

//MODで割ったあまりの演算
struct Rational {
	int r;
	Rational(int rr) :r(rr) {
	}
	Rational() = default;		//vectorに入れたりするときに必要
	operator int() {
		return r;
	}
	Rational operator+(const Rational& other)const {
		Rational res(0);
		res.r = r + other.r;
		modify(res.r);
		return res;
	}
	Rational operator-(const Rational& other)const {
		Rational res(0);
		res.r = r - other.r;
		modify(res.r);
		return res;
	}
	Rational operator*(const Rational& other) const {
		Rational res(0);
		res.r = r * other.r;
		modify(res.r);
		return res;
	}
	Rational operator/(const Rational& other)const {
		Rational res(0), res1(0);
		res = *this;
		res1.r = modInv(other.r);
		res = (*this) * res1;
		modify(res.r);
		return res;
	}
	void operator+=(const Rational& other) {
		*this = *this + other;
	}
	void operator-=(const Rational& other) {
		*this = *this - other;
	}
	void operator*=(const Rational& other) {
		*this = *this * other;
	}
	void operator/=(const Rational& other) {
		*this = *this / other;
	}
};

Rational pow(Rational r, int N) {
	if (N == 0)return Rational(1);
	if (N % 2 == 1)return r * pow(r, N - 1);
	Rational tmp = pow(r, N / 2);
	return tmp * tmp;
}
Rational operator"" _r(unsigned long long val) {
	return Rational(val);
}

/////////////////////

//KMP文字列検索
//計算量:O(|S|+|W|)
//ボイヤームーアは実務では良くても競プロでは使ってはいけない(最悪ケースで二乗オーダ)
struct KMP {
	std::string W;	//検索する文字列
	std::vector<int> T;	//テーブル
public:
	//計算量:O(|W|)
	KMP(const std::string& W_) :W(W_) {
		T.resize(W.size() + 1);
		int i = 2;		//T の中で現在計算している位置
		int j = 0;		//現在見ているサブ文字列の次の文字のインデックス。0から始まる
		//先頭ふたつの値は固定。ただしアルゴリズムの実装によっては具体的値は異なる
		T[0] = -1;
		if (2 <= W.size()) {
			T[1] = 0;
		}
		while (i <= W.size()) {
			if (W[i - 1] == W[j]) {
				T[i] = j + 1;
				i = i + 1;
				j = j + 1;
			}
			else if (j > 0) {
				j = T[j];
			}
			else {
				T[i] = 0;
				i = i + 1;
			}
		}
	}
	//return: W が見つかった際の S 内の位置を全列挙(先端が0番目)
	//全列挙でも一個探す場合と計算量的に変わらない
	//(むしろ一個探す実装を繰り返して全列挙するとTLEする)
	//Sを変えて複数回呼べる
	//計算量:O(|S|)
	std::vector<int> searchAll(const std::string& S)const {
		std::vector<int>res;
		//S 内の現在照合中の開始位置
		int m = 0;
		//W 内の現在位置
		int i = 0;
		while (m + i < S.size()) {
			if (W[i] == S[m + i]) {
				++i;
				if (i == W.size()) {
					res.push_back(m);
				}
				else {
					continue;
				}
			}
			m = m + i - T[i];
			if (i > 0) {
				i = T[i];
			}
		}
		return res;
	}
};

//Z-Algorithm(「SとSの後半」の接頭辞の長さ)
std::vector<int> Zalgorithm(const std::string& S) {
	std::vector<int> res(S.size());
	int c = 0;
	for (int i = 1; i < S.size(); i++) {
		if (i + res[i - c] < c + res[c]) {
			res[i] = res[i - c];
		}
		else {
			int j = std::max({ 0LL, c + res[c] - i });
			while (i + j < S.size() && S[j] == S[i + j]) ++j;
			res[i] = j;
			c = i;
		}
	}
	res[0] = S.size();
	return res;
}

//
namespace rollingHashConfig {
//複数の素数を試し衝突を回避
static constexpr int N = 3;
static const  std::array<std::uint64_t, N>Ms = { 2147483647  , 4444444447, 1234567891 };	//素数
static const  std::array<std::uint64_t, N> B = { 8127,8128,114514 };
} //namespace rollingHashConfig

struct RollingHashResult {
	std::array<std::uint64_t, rollingHashConfig::N>hashes;
	bool operator==(const RollingHashResult& other)const {
		for (int i = 0; i < rollingHashConfig::N; ++i) {
			if (hashes[i] != other.hashes[i])return false;
		}
		return true;
	}
	bool operator<(const RollingHashResult& other)const {
		for (int i = 0; i < rollingHashConfig::N; ++i) {
			if (hashes[i] < other.hashes[i])return true;
			if (hashes[i] > other.hashes[i])return false;
		}
		return false;
	}
};

//hash合成
size_t hashCombine(size_t seed0, size_t seed1) {
	return seed0 ^ (seed1 + 0x9e3779b9 + (seed0 << 6) + (seed0 >> 2));
}

namespace std {
//unordered_set用
template<>
struct hash<RollingHashResult> {
public:
	size_t operator()(const RollingHashResult& data)const {
		std::size_t seed = 0;
		for (int i = 0; i < rollingHashConfig::N; ++i) {
			seed = hashCombine(seed, data.hashes[i]);
		}
		return seed;
	}
};
}

struct RollingHash {
	std::array < std::vector<std::uint64_t>, rollingHashConfig::N> hashed, power;
	RollingHash(const std::string& s) {
		int sz = (int)s.size();
		for (int i = 0; i < rollingHashConfig::N; ++i) {
			hashed[i].assign(sz + 1, 0);
			power[i].assign(sz + 1, 0);
			power[i][0] = 1;
			for (int j = 0; j < sz; ++j) {
				std::uint64_t base = rollingHashConfig::B[i];
				std::uint64_t mod = rollingHashConfig::Ms[i];
				power[i][j + 1] = (power[i][j] * base) % mod;
				hashed[i][j + 1] = ((hashed[i][j] * base) % mod + (std::uint64_t)s[j]) % mod;
			}
		}
	}
	RollingHashResult get(int offset, int size) {
		int l = offset;
		int r = offset + size;
		RollingHashResult res;
		for (int i = 0; i < rollingHashConfig::N; ++i) {
			std::uint64_t mod_ = rollingHashConfig::Ms[i];
			//符号なしなので負になったりオーバーフローしないように細心の注意が必要
			res.hashes[i] = (hashed[i][r] + mod_ - (hashed[i][l] * power[i][r - l]) % mod_) % mod_;
		}
		return res;
	}
};



//Manacher:回文アルゴリズム(未実装)



//累積和
std::vector<int> MAKESUM(const std::vector<int>& A) {
	std::vector<int>res(A.size() + 1);
	res[0] = 0;
	for (int i = 1; i < A.size() + 1; ++i) {
		res[i] = res[i - 1] + A[i - 1];
	}
	return res;
}

//セグメント木
struct SegmentTree {
	std::vector<int>val;
	size_t size;
public:
	SegmentTree(size_t sz) {
		//2の累乗でないといけない
		assert((sz & (sz - 1)) == 0);
		//
		val.resize(sz * 2 - 1);
		size = sz;
	}
	void fill(int v) {
		std::fill(val.begin(), val.end(), v);
	}
	//TODO 全部に初期値を入れてからやるばあいはまとめて更新するとO(N)でできる
	//	setをN回呼ぶとNlogNかかる

	//群の演算
	static int operate(int a, int b) {
		return a + b;
	}
	//群の単位元
	static int unit() {
		return 0;
	}
	//idの値を変更
	void set(int idx, int v) {
		assert(0 <= idx && idx < size);
		int offset = size;
		val[offset - 1 + idx] = v;
		int segSize = 1;
		while (offset > 1) {
			val[offset / 2 - 1 + idx / segSize / 2]
				= SegmentTree::operate(val[offset - 1 + idx / segSize / 2 * 2 + 0], val[offset - 1 + idx / segSize / 2 * 2 + 1]);
			offset /= 2;
			segSize *= 2;
		}
	}
	int query(int a, int b, int k, int l, int r) {
		// https://www.slideshare.net/iwiwi/ss-3578491 を参考にした
		if (r <= a || b <= l) return unit();
		// 交差しない？
		if (a <= l && r <= b) return val[k];
		// 完全に含む？
		else {
			int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return operate(vl, vr);
		}

	}
	void query2(int a, int b, int k, int l, int r, int vl) {
		// https://www.slideshare.net/iwiwi/ss-3578491 を参考にした
		if (r <= a || b <= l) return;
		// 交差しない？
		if (a <= l && r <= b) {
			val[k] = vl;
		}
		// 完全に含む？
		else {
			query2(a, b, k * 2 + 1, l, (l + r) / 2, vl);
			query2(a, b, k * 2 + 2, (l + r) / 2, r, vl);
		}

	}
	//[a,b)のoperateの結果を得る
	//max,gcdなど逆演算ができないものを考慮すると[0,a)が取得できるだけでは不十分
	int get(int a, int b) {
		return query(a, b, 0, 0, size);
	}
	//区間[a,b)の値を変更
	void set(int a, int b, int val) {
		return query2(a, b, 0, 0, size, val);
	}
};


int TLE() {
	volatile int res = 0;
	for (int i = 0; i < INF; ++i) {
		res += i;
	}
	return res;
}
void MLE() {
	//なぜかvolatile auto *p =new char[N]ではMLEにならない(多分gcc O2の最適化)
	constexpr int N = 1024 * 1024 * 1024;
	std::vector<char>v(N);
	v.back() = 0;		//最適化防止？
}
//ジャッジが遅い
void OLE() {
	for (int i = 0; i < INF; ++i) {
		//endlを出力するとWAになる？
		//数字を出力した方がいい？
		//ストリーム版だとTLEになる？
		printf("8127\n");
	}
}
void RE() {
	throw 1000000007;
}


template <class T>
int SZ(const T& x) {
	return (int)x.size();
}

template <class T>
void PRINT(const T& con) {
	cout << "(";
	for (auto& one : con) {
		cout << one << ",";
	}
	cout << ")" << endl;
}

//a以上の整数でmで割ってk余る最小の数
//(b以下の最大の数が欲しい場合は適宜帰着して使う)
int minimumMod(int a, int m, int k) {
	int res = (a - k) / m * m + k;
	if (a <= res - m)return res - m;
	if (a <= res)return res;
	return res + m;
}



template <class Itr>
using HuffmanVal = typename std::remove_reference<decltype(*std::declval<Itr>())>::type;

//ハフマン圧縮
template <class Itr>
std::vector<std::pair<HuffmanVal<Itr>, int>> haffman(Itr begin, Itr end) {
	std::vector<std::pair<HuffmanVal<Itr>, int>> res;
	bool first = true;
	HuffmanVal<Itr> now = {};
	int count = 0;
	for (auto itr = begin; itr != end; ++itr) {
		if (now != *itr && !first) {
			res.push_back({ now,count });
			count = 0;
		}
		first = false;
		now = *itr;
		++count;
	}
	if (count > 0) {
		res.push_back({ now,count });
	}
	return res;
}

//座標(0,0)(a,0)(b,c),0<b<a,0<c
struct TriangleRes {
	double a, b, c;
};

//三角形を回転して正規化
TriangleRes triangleRegularization(int x0, int y0, int x1, int y1, int x2, int y2) {
	int len0 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
	int len1 = (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0);
	int len2 = (x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1);
	//len2が最長の辺になるようにする
	if (len0 > len2) {
		std::swap(x0, x2);
		std::swap(y0, y2);
		std::swap(len0, len2);
	}
	if (len1 > len2) {
		std::swap(x1, x2);
		std::swap(y1, y2);
		std::swap(len1, len2);
	}
	//頂点0を原点に移動
	x1 -= x0;
	x2 -= x0;
	x0 = 0;
	y1 -= y0;
	y2 -= y0;
	y0 = 0;
	//回転
	double cos = x1 / hypot(x1, y1);
	double sin = -y1 / hypot(x1, y1);
	TriangleRes res;
	res.a = x1 * cos - y1 * sin;
	res.b = x2 * cos - y2 * sin;
	res.c = x2 * sin + y2 * cos;
	//
	if (res.c < 0) {
		res.b = res.a - res.b;
		res.c *= -1;
	}
	return res;
}


constexpr double pi = 3.141592653589793238462;
//////////////////

#define LOADVEC(type,name,N) std::vector<type>name(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name[nnn]; \
}

#define LOADVEC2(type,name0,name1,N) std::vector<type>name0(N),name1(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn]; \
}

#define LOADVEC3(type,name0,name1,name2,N) std::vector<type>name0(N),name1(N),name2(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn];cin >> name2[nnn]; \
}

#define LOAD(type,name) type name; \
cin >> name;

void makeInput() {
	int N = 100;
	int M = 120;
	cout << N << " " << M << endl;
	for (int i = 1; i <= N; ++i) {
		cout << N * M - rand() % i - i + 1;
		if (i != N)cout << " ";
	}
	cout << endl;
	for (int i = 1; i <= M; ++i) {
		cout << N * M - rand() % i - i + 1;
		if (i != M)cout << " ";
	}
	cout << endl;
}


void proc();

signed main() {
	ios::sync_with_stdio(false);
	std::cout << std::setprecision(30);
	proc();
	//makeInput();
	return 0;
}

/*
--------------------------------------------------------
--------------------------------------------------------
---------------    template      ----------------------
--------------------------------------------------------
--------------------------------------------------------
*/



#if 0

struct S {
	int dis = -1;
};

template<class T>
void Graph<T>::dfsCustom(int pos, int prev) {
	int nEdge = 0;
	for (auto& e : vertex[pos].edges) {
		const int next = e.next;
		if (next == prev) continue;
		if (val(next).dis == -1) {
			val(next).dis = val(pos).dis + 1;
			dfsCustom(next, pos);
			++nEdge;
		}
		else if (val(next).dis < val(pos).dis) {
			//ここに来たなら木ではない(後退辺の処理)
			assert(false);
		}
	}
	//
	int rat = K - 1;
	if (val(pos).dis == 0) {
		for (int i = 0; i < nEdge; ++i) {
			res *= rat;
			modify(res);
			--rat;
		}
	}
	else {
		--rat;
		for (int i = 0; i < nEdge; ++i) {
			res *= rat;
			modify(res);
			--rat;
		}
	}
}

#endif



void proc() {
	LOAD(int, N);
	LOAD(int, T);
	LOADVEC2(int, A, B, N);
	struct Data {
		int val;
	};
	std::vector<std::vector<Data>> dp(N + 1);
	for (int i = 0; i < N + 1; ++i) {
		dp[i].resize(T + 1);
	}



	// DP初期条件: dp[0][w] = 0
	for (int w = 0; w <= T; ++w) dp[0][w].val = 0;

	// DPループ
	for (int i = 0; i < N; ++i) {
		for (int w = 0; w <= T; ++w) {
			if (w >= A[i]) {
				if (dp[i][w - A[i]].val + B[i] > dp[i][w].val) {
					dp[i + 1][w] = dp[i][w - A[i]];
					dp[i + 1][w].val += B[i];
				}
				else {
					dp[i + 1][w] = dp[i][w];
				}
			}
			else {
				dp[i + 1][w] = dp[i][w];
			}
		}
	}
	std::unordered_set<int>s;
	int t = T - 1;
	for (int i = N; 1 <= i; --i) {
		if (dp[i][t].val == dp[i - 1][t].val) {

		}
		else {
			t -= A[i - 1];
			s.insert(i - 1);
		}
	}
	int m = 0;
	for (int i = 0; i < N; ++i) {
		auto itr = s.find(i);
		if (itr == s.end()) {
			chmax(m, B[i]);
		}
	}


	cout << dp[N][T - 1].val + m << endl;


}
#endif




Measured memory_bytes: 70912