結果
| 問題 | No.951 【本日限定】１枚頼むともう１枚無料！ |
| ユーザー |
 warabi0906
|
| 提出日時 | 2023-03-14 20:59:39 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 21,819 bytes |
| コンパイル時間 | 3,010 ms |
| コンパイル使用メモリ | 219,228 KB |
| 実行使用メモリ | 421,632 KB |
| 最終ジャッジ日時 | 2024-09-18 08:25:06 |
| 合計ジャッジ時間 | 15,274 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 13 ms
30,196 KB |
| testcase_01 | AC | 13 ms
30,192 KB |
| testcase_02 | AC | 12 ms
30,336 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 257 ms
302,976 KB |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | AC | 386 ms
421,504 KB |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | AC | 11 ms
30,336 KB |
| testcase_31 | AC | 12 ms
30,208 KB |
| testcase_32 | AC | 14 ms
32,364 KB |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | AC | 370 ms
421,504 KB |
| testcase_36 | AC | 366 ms
421,504 KB |
| testcase_37 | AC | 367 ms
421,504 KB |
| testcase_38 | AC | 366 ms
421,504 KB |
| testcase_39 | WA | - |
| testcase_40 | AC | 362 ms
421,504 KB |
| testcase_41 | AC | 361 ms
421,472 KB |
| testcase_42 | AC | 359 ms
421,504 KB |
| testcase_43 | AC | 361 ms
421,504 KB |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | AC | 365 ms
421,504 KB |
| testcase_47 | AC | 362 ms
421,440 KB |
| testcase_48 | AC | 365 ms
421,420 KB |
| testcase_49 | AC | 366 ms
421,632 KB |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | AC | 365 ms
421,384 KB |
ソースコード
/*
Hi,I am warabi.
Welcome to my coding space.
Let me give you a great word of advice.
"The pen is mightier than the sword"
-by Edward Bulwer-Lytton
_,,....,,_ ＿人人人人人人人人人人人人人人人人人人＿
-''":::::::::::::｀''＞ ゆっくりできるとでも? ＜
ヽ:::::::::::::::::::::￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ￣
|::::::;ノ´￣＼:::::::::::＼_,. -‐ｧ ＿_ _____ ＿_____
|::::ﾉ ヽ､ヽr-r'"´ （.__ ,´ _,, '-´￣￣｀-ゝ 、_ イ、
_,.!イ_ _,.ﾍｰｧ'二ﾊ二ヽ､へ,_7 'r ´ ヽ、ﾝ、
::::::rｰ''7ｺ-‐'"´ ; ', ｀ヽ/｀7 ,'＝=─- -─=＝', i
r-'ｧ'"´/ /! ﾊ ハ ! iヾ_ﾉ i ｲ iゝ、ｲ人レ／_ルヽｲ i |
!イ´ ,' | /__,.!/ V ､!__ﾊ ,' ,ゝ ﾚﾘｲi (ﾋ_] ﾋ_ﾝ ).| .|、i .||
`! !/ﾚi' (ﾋ_] ﾋ_ﾝ ﾚ'i ﾉ !Y!"" ,＿__, "" 「 !ﾉ i |
,' ﾉ !'" ,＿__, "' i .ﾚ' L.',. ヽ _ﾝ L」 ﾉ| .|
（ ,ﾊ ヽ _ﾝ 人! | ||ヽ、 ,ｲ| ||ｲ| /
,.ﾍ,）､ ）＞,､ _____, ,.イ ハ レ ル｀ ー--─ ´ルﾚ ﾚ´
Take your time.
GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define V vector
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define brep(i,a,b) for(ll i=a;i>=b;i--)
#define reph(i,vec) for(auto &i:vec)
#define FI first
#define SE second
#define P pair
#define PB push_back
#define INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ins(name) string name;cin >> name;
#define inc(name) char name;cin >> name
#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}
#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}
#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}
#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i
#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;
#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE
#define out(n) cout << (n) << endl
#define _out(n) cout << " " << (n) << endl;
#define notout(n) cout << (n)
#define out_(n) cout << (n) << " "
#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";
#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;
#define new_line cout<<endl;
#define getbit(n,k) (((1LL<<(k))&(n))>0)
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 998244353
#define CMOD MOD2
#define EPS 0.00000001
//debug
#define bug assert(false);
#define debug out("this point ok");
//
//constexpr long double PI=3.14159265358979323846;
//template
template<typename T>
inline bool chmax(T &a,const T b){if(a<b){a=b;return true;}return false;}
template<typename T>
inline bool chmin(T &a,const T b){if(a>b){a=b;return true;}return false;}
//
namespace Warabi{
//常備変数のコーナー
V<bool> primes(3001000,true);
V<ll> prime_list;
V<ll> prime_rui(3001000,0LL);
V<bool> visiteded(300100);
V<bool> afed(300100,false);
V<ll> k1(200100,0ll);
V<ll> k2(200100,0ll);
//
//常備構造体宣言のコーナー
class UnionFind {
private:
ll NumberOfElements;
ll Not1NumberOfelements;
public:
vector<ll> par;
vector<ll> SIZE;
vector<bool> loop;
void init(ll sz) {
par.resize(sz, -1LL);
SIZE.resize(sz,1LL);
loop.resize(sz,false);
NumberOfElements=sz;
Not1NumberOfelements=0ll;
}
ll root(ll pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
bool same(ll u, ll v) {
if (root(u) == root(v)) return true;
return false;
}
ll SZ(ll u){
return SIZE[root(u)];
}
ll noe(){
return NumberOfElements;
}
ll nnoe(){
return Not1NumberOfelements;
}
bool unite(ll u, ll v) {
u = root(u); v = root(v);
if (u == v){
if(loop[u]==true){
out("No");
exit(0);
}
loop[u]=true;
return false;
}
if(SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;
par[u] = v;
SIZE[v] += SIZE[u];
NumberOfElements--;
return true;
}
};
class SCC{
public:
V<V<ll>> G;
V<V<ll>> UG;
V<ll> order;
V<ll> GROUP;
V<bool> visited;
ll sz_count;
V<ll> groupsize;
void init(ll sz){
G.resize(sz,V<ll>(0));
UG.resize(sz,V<ll>(0));
GROUP.resize(sz,-1ll);
visited.resize(sz,false);
sz_count=0LL;
return;
}
void dfs(ll now){
visited[now]=true;
reph(i,G[now]){
if(visited[i])continue;
dfs(i);
}
order.PB(now);
return;
}
void dfs2(ll now,ll group){
GROUP[now]=group;
sz_count++;
reph(i,UG[now]){
if(GROUP[i]!=-1ll and GROUP[i]!=group)continue;
if(GROUP[i]!=-1ll)continue;
dfs2(i,group);
}
return;
}
void make_group(V<V<ll>> Graph_function){
G=Graph_function;
rep(i,0,(ll)G.size()){
reph(j,G[i]){
UG[j].PB(i);
}
}
rep(i,0,(ll)G.size()){
if(visited[i])continue;
dfs(i);
}
reverse(all(order));
ll now_group=0LL;
reph(i,order){
if(GROUP[i]!=-1)continue;
ll prev=sz_count;
dfs2(i,now_group);
now_group++;
groupsize.PB(sz_count-prev);
}
return;
}
};
template<typename X,typename M>
class SegmentTree{
public:
long long sz;
using FX=function<X(X,X)>;
using FA=function<X(X,M)>;
using FM=function<M(M,M)>;
const FX fx;
const FA fa;
const FM fm;
const X ex;
const M em;
vector<X> node;
vector<M> lazy;
SegmentTree(long long sz_,FX fx_,FA fa_,FM fm_,X ex_,M em_):sz(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_){
long long n=1LL;
while(n<sz_)n*=2;
sz=n;
node.resize(sz*2-1,ex);
lazy.resize(sz*2-1,em);
}
void set(long long index,X x){
node[index+sz-1]=x;
return;
}
void build(){
for(int i=sz-2;i>=0;i--)node[i]=fx(node[i*2+1],node[i*2+2]);
return;
}
void eval(long long k){
if(lazy[k]==em)return;
if(k<sz-1){
lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]);
lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]);
}
node[k]=fa(node[k],lazy[k]);
lazy[k]=em;
}
void update_sub(long long a,long long b,M x,long long k,long long l,long long r){
//cout << " " << a << " " << b << " " << l << " " << r << endl;
eval(k);
if(a<=l and r<=b){
lazy[k]=fm(lazy[k],x);
//cout<<" "<<lazy[k]<<endl;
eval(k);
return;
}
else if(a<r and l<b){
update_sub(a,b,x,k*2+1,l,(l+r)/2);
update_sub(a,b,x,k*2+2,(l+r)/2,r);
node[k]=fx(node[k*2+1],node[k*2+2]);
return;
}
return;
}
void update(long long a,long long b,M x){
update_sub(a,b,x,0LL,0LL,sz);
return;
}
void add_sub(long long a,X x,long long k,long long l,long long r){
eval(k);
node[k]+=x;
if(k<sz-1){
long long mid=(l+r)/2;
if(a<mid)add_sub(a,x,k*2+1,l,mid);
else add_sub(a,x,k*2+2,mid,r);
}
return;
}
void add(long long a,X x){
add_sub(a,x,0LL,0LL,sz);
}
X query_sub(long long a,long long b,long long k,long long l,long long r){
eval(k);
if(r<=a or b<=l)return ex;
else if(a<=l and r<=b)return node[k];
else{
X Xl=query_sub(a,b,k*2+1,l,(l+r)/2);
X Xr=query_sub(a,b,k*2+2,(l+r)/2,r);
//cout<<" / "<<Xl<<" "<<Xr<<endl;
return fx(Xl,Xr);
}
}
X query(long long a,long long b){
return query_sub(a,b,0LL,0LL,sz);
}
inline X operator [] (long long index){
return query(index,index+1);
}
};
template<typename T>
class multimap{
private:
map<T,ll> mp;
public:
void add(ll x){
mp[x]++;
return;
}
void del(ll x){
mp[x]--;
if(mp[x]<1)mp.erase(x);
return;
}
T maximum(){
return mp.rbegin()->first;
}
T minimum(){
return mp.begin()->first;
}
};
class LCA{
public:
vector<vector<long long>> parent;
vector<long long> dist;
vector<vector<long long>> G;
LCA(const vector<vector<long long>> &gr){init(gr);}
void dfs(long long v,long long p,long long d){
parent[0][v]=p;
dist[v]=d;
for(long long next : G[v]){
if(next==p)continue;
dfs(next,v,d+1);
}
return;
}
void init(const vector<vector<long long>> &gr){
G=gr;
parent.assign(33,vector<long long>(G.size(),-1LL));
dist.assign(G.size(),-1LL);
dfs(0LL,-1LL,0LL);
for(int i=0;i<32;i++){
for(int j=0;j<(int)G.size();j++){
if(parent[i][j]<0LL){
parent[i+1][j]=-1LL;
}
else{
parent[i+1][j]=parent[i][parent[i][j]];
}
}
}
return;
}
long long lca(long long u,long long v){
if(dist[u]<dist[v])swap(u,v);
long long between=dist[u]-dist[v];
for(int i=0;i<33;i++){
if(between&(1LL<<i)){u=parent[i][u];}
}
if(u==v)return u;
for(int i=32;i>=0;i--){
if(parent[i][u]!=parent[i][v]){
u=parent[i][u];
v=parent[i][v];
}
}
assert(parent[0][u]==parent[0][v]);
return parent[0][u];
}
long long get_dist(long long u,long long v){
return dist[u]+dist[v]-2*dist[lca(u,v)];
}
bool on_path(long long u,long long v,long long a){
return get_dist(u,v)==get_dist(u,a)+get_dist(v,a);
}
};
class nCk {
public:
const long long m;
const long long MAXIMUM = 1000000;
vector<long long> fac, facinv, inv;
nCk(long long m_);
~nCk();
long long com(long long n, long long k)const;
long long com_(vector<long long> vec)const;
};
nCk::nCk(long long m_):m(m_) {
fac.resize(MAXIMUM + 3);
facinv.resize(MAXIMUM + 3);
inv.resize(MAXIMUM + 3);
fac[0] = fac[1] = 1;
facinv[0] = facinv[1] = 1;
inv[1] = 1;
for (long long i = 2; i < MAXIMUM + 2; i++) {
fac[i] = fac[i - 1] * i % m;
inv[i] = m - inv[m % i] * (m / i) % m;
facinv[i] = facinv[i - 1] * inv[i] % m;
}
}
nCk::~nCk(){}
long long nCk::com(long long n, long long k)const {
if(k==0)return 1;
if (n < k)return 0LL;
assert(!(n < 0 || k < 0));
return fac[n] * (facinv[k] * facinv[n - k] % m) % m;
}
long long nCk::com_(vector<long long> vec)const{
long long sz=(long long)vec.size();
long long sum=0LL;
for(const long long v:vec)sum+=v;
long long res=1LL;
for(long long i=0;i<sz;i++){
res*=com(sum,vec[i]);
res%=m;
sum-=vec[i];
}
return res;
}
//
//常備構造体宣言のコーナー
struct STC{
ll s,t,cost;
};
//
//常備関数のコーナー
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}
//木の直径を求める
STC Cdiameter(V<V<P<ll,ll>>> G,ll start,bool type){
visiteded=afed;
queue<ll> sirabe;
sirabe.push(start);
V<ll> short_load(G.size(),0LL);
while(!sirabe.empty()){
ll s=sirabe.front();
sirabe.pop();
visiteded[s]=true;
reph(i,G[s]){
if(visiteded[i.FI])continue;
short_load[i.FI]=short_load[s]+i.SE;
sirabe.push(i.FI);
}
}
ll far_max=-1LL;
ll element=-1LL;
rep(i,0,(ll)G.size()){
if(far_max>=short_load[i])continue;
far_max=short_load[i];
element=i;
}
if(type)return Cdiameter(G,element,false);
else return {start,element,far_max};
}
//素数の取得
void prime_init(){
V<bool> at(3001000,true);
primes=at;
primes[0]=primes[1]=false;
rep(i,2,3000100){
if(!primes[i])continue;
for(ll j=i*2;j<=300100;j+=i)primes[j]=false;
}
rep(i,1,3000100){
if(primes[i]){
prime_list.PB(i);
prime_rui[i]=prime_rui[i-1]+1;
}
else{
prime_rui[i]=prime_rui[i-1];
}
}
return;
}
//modpow
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 63; i++) {
if ((b & (1LL << i)) != 0) {
p *= q;
p %= m;
}
q *= q;
q %= m;
}
return p;
}
//逆元
long long Div(long long a, long long b, long long m) {
return (a * modpow(b, m - 2, m)) % m;
}
//点と点の距離を返す
long double Dis(ll ax,ll ay,ll bx,ll by){
return sqrt(pow(ax-bx,2)+pow(ay-by,2));
}
//二つのベクトルから平行四辺形の面積を返す
ll he(ll x0,ll y0,ll x1,ll y1,ll x2,ll y2){//外積を二で割る
return abs((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0));
}
//
template<typename T>
ll Lis_size(V<T> arr,ll sz){
const T TINF=numeric_limits<T>::max();
V<T> DP(sz+1,TINF);
DP[0]=-TINF;
rep(i,0,sz){
*lower_bound(all(DP),arr[i])=arr[i];
}
ll ans=0LL;
rep(i,1,sz+1){
if(DP[i]!=TINF)ans=i;
}
return ans;
}
string toBinary(ll n){
string r;
while (n != 0LL){
r += ( n % 2LL == 0LL ? "0" : "1" );
n /= 2LL;
}
return r;
}
template<typename T>
V<ll> press(V<T> arr){
V<T> X=arr;
sort(all(X));
X.erase(unique(all(X)),X.end());
V<ll> ans(arr.size());
rep(i,0LL,(ll)arr.size()){
ans[i]=lower_bound(all(X),arr[i])-X.begin();
}
return ans;
}
P<V<V<ll>>,V<V<P<ll,ll>>>> warshall_floyd(ll N,V<V<P<ll,ll>>> G){
V<V<ll>> DP(N,V<ll>(N,INF));
rep(i,0,N)DP[i][i]=0LL;
V<V<P<ll,ll>>> prev(N,V<P<ll,ll>>(N,{INF,INF}));
rep(i,0,N){
reph(j,G[i]){
DP[i][j.FI]=j.SE;
prev[i][j.FI]={i,j.FI};
}
}
rep(k,0,N){
rep(i,0,N){
rep(j,0,N){
if(chmin(DP[i][j],DP[i][k]+DP[k][j])){
prev[i][j]=prev[k][j];
}
}
}
}
return {DP,prev};
}
template<typename T>
void to_sum(V<T> &arr){
rep(i,0,(ll)arr.size()-1LL){
arr[i+1]+=arr[i];
}
return;
}
template<typename T>
void including_map(ll H,ll W,V<V<T>> &G,T c){
V<V<T>> new_G(H+2,V<T>(W+2));
rep(i,0,W+2)new_G[0][i]=c;
rep(i,1,H+1){
new_G[i][0]=c;
new_G[i][W+1]=c;
rep(j,1,W+1){
new_G[i][j]=G[i-1][j-1];
}
}
rep(i,0,W+2)new_G[H+1][i]=c;
G=new_G;
return;
}
struct BIT {
private:
vector<int> bit;
int N;
public:
BIT(int size) {
N = size;
bit.resize(N + 1);
}
// 一点更新です
void add(int a, int w) {
for (int x = a; x <= N; x += x & -x) bit[x] += w;
}
// 1~Nまでの和を求める。
int sum(int a) {
int ret = 0;
for (int x = a; x > 0; x -= x & -x) ret += bit[x];
return ret;
}
};
ll fall_down(ll n,const V<ll> &v){
ll ans = 0;
BIT b(n); // これまでの数字がどんな風になってるのかをメモる為のBIT
for (int i = 0; i < n; i++) {
ans += i - b.sum(v[i]); // BITの総和 - 自分より左側 ＝ 自分より右側
b.add(v[i], 1); // 自分の位置に1を足す
}
return ans;
}
set<ll> factor(ll N){
set<ll> ans;
for(ll i=1LL;i*i<=N;i++){
if(N%i)continue;
ans.INS(i);
ans.INS(N/i);
}
return ans;
}
V<ll> dijkstra(ll sz,V<V<P<ll,ll>>> G,ll s){
V<ll> ans(sz,INF);ans[s]=0LL;
priority_queue<P<ll,ll>,vector<P<ll,ll>>,greater<P<ll,ll>>> examine;
examine.push({0LL,s});
while(examine.size()){
P<ll,ll> p=examine.top();
examine.pop();
ll now=p.SE,dist=p.FI;
if(ans[now]<dist)continue;
reph(i,G[now]){
ll next=i.FI,c=i.SE;
if(chmin(ans[next],dist+c)){
examine.push({dist+c,next});
}
}
}
return ans;
}
set<ll> pass(const V<V<ll>> &G,ll s,ll t){
V<bool> visited(G.size(),false);
set<ll> ans,res;
function<void(ll)> dfs=[&](ll now){
visited[now]=true;
res.INS(now);
if(now==t){
ans=res;
}
reph(next,G[now]){
if(visited[next])continue;
dfs(next);
}
res.erase(now);
return;
};
dfs(s);
return ans;
}
// 負の数にも対応した mod (a = -11 とかでも OK)
inline long long mod(long long a, long long m) {
long long res = a % m;
if (res < 0) res += m;
return res;
}
// 拡張 Euclid の互除法
long long extGCD(long long a, long long b, long long &p, long long &q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGCD(b, a%b, q, p);
q -= a/b * p;
return d;
}
long long extGcd(long long a, long long b, long long &p, long long &q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGcd(b, a%b, q, p);
q -= a/b * p;
return d;
}
// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
long long x, y;
extGCD(a, m, x, y);
return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}
// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
// coeffs[k] = m[0]m[1]...m[k-1]
// constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {
m.push_back(Mmod); // banpei
vector<long long> coeffs((int)m.size(), 1);
vector<long long> constants((int)m.size(), 0);
for (int k = 0; k < (int)b.size(); ++k) {
long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
for (int i = k+1; i < (int)m.size(); ++i) {
(constants[i] += t * coeffs[i]) %= m[i];
(coeffs[i] *= m[k]) %= m[i];
}
}
return constants.back();
}
pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {
long long r = 0, M = 1;
for (int i = 0; i < (int)b.size(); ++i) {
long long p, q;
long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
if ((b[i] - r) % d != 0) return make_pair(0, -1);
long long tmp = (b[i] - r) / d * p % (m[i]/d);
r += M * tmp;
M *= m[i]/d;
}
return make_pair(mod(r, M), M);
}
map<ll,ll> bunkai(ll n){
map<ll,ll> ans;
for(int i=2;i*i<=n;i++){
while(n%i==0){
if(n!=i)ans[n/i]++;
n/=i;
ans[i]++;
}
}
if(n>1)ans[n]++;
return ans;
}
template<typename T>
void RLE(vector<T> &arr){
vector<T> res;
res.push_back(arr[0]);
for(const T t:arr){
if(res.back()!=t)res.push_back(t);
}
arr=res;
return;
}
}
//
//構造体宣言のコーナー
struct P2{
ll l,r;
};
bool operator < (P2 a,P2 b){
if(a.r<b.r)return true;
if(a.r==b.r and a.l<b.l)return true;
return false;
}
class nCk_a{
public:
vector<long long> fact_inv, inv;
void init_nCk(int SIZE) {
fact_inv.resize(SIZE + 5);
inv.resize(SIZE + 5);
fact_inv[0] = fact_inv[1] = 1;
inv[1] = 1;
for (int i = 2; i < SIZE + 5; i++) {
inv[i] = MOD2 - inv[MOD2 % i] * (MOD2 / i) % MOD2;
fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD2;
}
}
long long com(int n, int k) {
assert(!(n < k));
assert(!(n < 0 || k < 0));
long long ans = 1;
for (int i = n; i >= n - k + 1; i--) {
ans *= i;
ans %= MOD2;
}
return ans * fact_inv[k] % MOD2;
}
};
long long gcd(long long a,long long b){
if(b==0LL)return a;
return gcd(b,a%b);
}
long long lcm(long long a,long long b){
return a*b/gcd(a,b);
}
int main(){
/*
文章を読み落としていませんか?
制約も隅々まで読んでいますか?
注意
・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
rは含みません
・BITって1-indexedなんだぜ
イケてるよな
・using namespace Warabi??
*/
//using namespace Warabi;
in(N);in(K);
V<P<ll,ll>> dat(N);
rep(i,0,N){
cin>>dat[i].FI>>dat[i].SE;
}
sort(all(dat));reverse(all(dat));
V<V<ll>> DP(N+1,V<ll>(2*K+5,0ll));//ピザiまでを選ぶか決め、j円使った場合の最大おいしさ
rep(i,0,N){
ll p=dat[i].FI,d=dat[i].SE;
rep(j,0,K+1){
chmax(DP[i+1][j],DP[i][j]);
if(i<N-1)chmax(DP[i+2][j+p],DP[i][j]+d+dat[i+1].SE);
else chmax(DP[i][j+p],DP[i][j]+d);
}
}
ll ans=0ll;
rep(j,0,K+1)chmax(ans,DP[N][j]);
out(ans);
}