#include <bits/stdc++.h>
using namespace std;

void solve(){
  int n,x;
  int w[101];
  cin>>n>>x;
  int sum=0;
  for (int i=0;i<n;i++){
    cin>>w[i];
    sum+=w[i];
  }
  //if the sum is x, we cannot avoid the explosion
  if (sum==x){
    cout<<"NO"<<endl;
    return;
  }
  cout<<"YES"<<endl;
  //otherwise, the answer always exists
  //we will keep adding elements from left to right
  //if we can't add element i, we add element i+1 first by swapping the two
  for (int i=0;i<n;i++){
    if (x==w[i]){
      //i+1 will always be less than n because otherwise, the total sum would be x
      swap(w[i],w[i+1]);
    }
    cout<<w[i]<<' ';
    x-=w[i];
  }
  cout<<endl;
  return;
}

int main(){
  int T; cin>>T;
  while (T--)
    solve();
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

bool isSquare(int x){
  int y=sqrt(x);
  return y*y==x;
}

void solve(){
  int n;
  cin>>n;
  if (n%2==0 && isSquare(n/2))
    cout<<"YES"<<endl;
  else if (n%4==0 && isSquare(n/4))
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
}

int main(){
  int t; cin>>t;
  while (t--)
    solve();
}

#include <bits/stdc++.h>
using namespace std;

int N,M,X;
int H[100001];

void solve(){
  cin>>N>>M>>X;
  cout<<"YES"<<endl;
  set<pair<int,int>>s; //stores pairs of (height, index)
  for (int i=1;i<=M;i++)
    s.insert({0,i});
  for (int i=0;i<N;i++){
    cin>>H[i];
    pair<int,int>p=*s.begin();
    s.erase(p);
    cout<<p.second<<' ';
    s.insert({p.first+H[i],p.second});
  }
  cout<<endl;
}

int main(){
  int T; cin>>T;
  while (T--)
    solve();
}

#include <bits/stdc++.h>
using namespace std;

int N,L,R;
int C[200001];
int lcnt[200001],rcnt[200001];

void solve(){
  cin>>N>>L>>R;
  for (int i=1;i<=N;i++){
    lcnt[i]=0;
    rcnt[i]=0;
  }
  for (int i=1;i<=N;i++){
    cin>>C[i];
    if (i<=L)
      lcnt[C[i]]++;
    else
      rcnt[C[i]]++;
  }
  //remove pairs that are already matching
  for (int i=1;i<=N;i++){
    int mn=min(lcnt[i],rcnt[i]);
    lcnt[i]-=mn;
    rcnt[i]-=mn;
    L-=mn;
    R-=mn;
  }
  if (L<R){
    swap(lcnt,rcnt);
    swap(L,R);
  }
  //now, there are at least as many left socks as right socks
  int ans=0;
  for (int i=1;i<=N;i++){
    int extra=L-R; //always even
    int canDo=lcnt[i]/2;
    int Do=min(canDo*2,extra);
    //turn "Do"/2 left socks of color i into right socks
    ans+=Do/2;
    L-=Do;
  }
  //turn extra lefts into rights, then adjust all colors
  ans+=(L-R)/2+(L+R)/2;
  cout<<ans<<endl;
}
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  int T; cin>>T;
  while (T--)
    solve();
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD;

int N;
ll dp[405][405];

ll fastexp(ll b, ll exp){
  if (exp==0)
    return 1;
  ll temp=fastexp(b,exp/2);
  temp=(temp*temp)%MOD;
  if (exp%2==1)
    temp*=b;
  return temp%MOD;
}

ll fact[405],inv[405],choose[405][405],pow2[405];

void precompute(){
  fact[0]=1;
  inv[0]=1;
  for (int i=1;i<=N;i++){
    fact[i]=(fact[i-1]*i)%MOD;
    inv[i]=fastexp(fact[i],MOD-2);
  }
  for (int i=0;i<=N;i++)
    for (int j=0;j<=i;j++)
      choose[i][j]=((fact[i]*inv[j])%MOD*inv[i-j])%MOD;
  for (int i=0;i<=N;i++)
    pow2[i]=fastexp(2,i);
}

int main()
{
  cin>>N>>MOD;
  precompute();
  dp[0][0]=1;
  for (int i=0;i<N;i++){
    for (int j=0;j<=i;j++){
      for (int k=1;i+k<=N;k++){
	dp[i+k+1][j+k]+=((dp[i][j]*pow2[k-1])%MOD*choose[j+k][k]);
	dp[i+k+1][j+k]%=MOD;
      }
    }
  }
  ll ans=0;
  for (int i=0;i<=N;i++)
    ans=(ans+dp[N+1][i])%MOD;
  cout<<ans<<endl;
  return 0;
}

// Fix a spanning tree
// Pick a leaf, either merge it into its parent or postpone it to the end
#include <cstdio>
#include <vector>
#include <algorithm>

const int MAXV=300005;
const int MAXE=300005;

int N,M,X;
long long as[MAXV];

int elist[MAXE*2];
int head[MAXV];
int prev[MAXE*2];
int tot=0;

bool vis[MAXV];

int ans[MAXV];
int front,back;

void dfs(int u){
  vis[u]=true;
  for(int e=head[u];e!=-1;e=prev[e]){
    int v=elist[e^1];
    if(vis[v]) continue;
    dfs(v);
    if(as[u]+as[v]>=X){
      as[u]+=as[v]-X;
      ans[front++]=e>>1;
    }else{
      ans[--back]=e>>1;
    }
  }
}

int main(){
  scanf("%d %d %d",&N,&M,&X);
  long long total=0;
  for(int i=0;i<N;i++){
    scanf("%lld",&as[i]);
    total+=as[i];
  }
  if(total<1LL*(N-1)*X){
    printf("NO\n");
    return 0;
  }
  std::fill(head,head+N,-1);
  for(int i=0;i<M*2;i++){
    int U;
    scanf("%d",&U);
    U--;
    prev[i]=head[U];
    head[U]=i;
    elist[i]=U;
  }
  back=N-1;
  dfs(0);
  printf("YES\n");
  for(int i=0;i<N-1;i++){
    printf("%d\n",ans[i]+1);
  }
}

#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>

using ll = long long;

std::vector<std::pair<int,int> > fwd[200005];
std::vector<std::pair<int,int> > rev[200005];

int vis[200005];
int cc[200005];
ll offset[200005];
int ncc;
ll loop[200005];
std::vector<int> ord;

ll gcd(ll a,ll b){
  return b?gcd(b,a%b):a;
}

void dfs_fwd(int x){
  vis[x]=1;
  for(auto e:fwd[x]){
    int y=e.first;
    if(vis[y]!=1){
      dfs_fwd(y);
    }
  }
  ord.push_back(x);
}

void dfs_rev(int x){
  vis[x]=2;
  for(auto e:rev[x]){
    int y=e.first,l=e.second;
    if(vis[y]!=2){
      cc[y]=cc[x];
      offset[y]=offset[x]+l;
      dfs_rev(y);
    }else if(cc[y]==cc[x]){
      loop[cc[x]]=gcd(loop[cc[x]],std::llabs(offset[x]+l-offset[y]));
    }
  }
}

int main(){
  int N,M;
  scanf("%d %d",&N,&M);
  for(int i=0;i<M;i++){
    int A,B,L;
    scanf("%d %d %d",&A,&B,&L);
    A--,B--;
    fwd[A].push_back({B,L});
    rev[B].push_back({A,L});
  }
  for(int i=0;i<N;i++){
    if(vis[i]!=1){
      dfs_fwd(i);
    }
  }
  std::reverse(ord.begin(),ord.end());
  for(int i:ord){
    if(vis[i]!=2){
      cc[i]=ncc++;
      offset[i]=0;
      dfs_rev(i);
    }
  }
  int Q;
  scanf("%d",&Q);
  for(int i=0;i<Q;i++){
    int V,S,T;
    scanf("%d %d %d",&V,&S,&T);
    V--;
    assert(0<=S&&S<T);
    if(S%gcd(loop[cc[V]],T)==0){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
}

#include <cstdio>
#include <cassert>
#include <utility>
#include <functional>

//numbers up to 2^MAXLOGX-1
const int MAXLOGX=20;

template<int k>
struct Trie{
  Trie<k-1>* chd[2];
  int cnt;
  int lazy;
  int has[2];
  int get_cnt(){
    assert(this!=NULL);
    return cnt;
  }
  int get_has(int d){
    assert(this!=NULL);
    push();
    assert(has[d]<(1<<(k+1)));
    return has[d];
  }
  Trie(Trie<k-1>* l,Trie<k-1>* r):chd{l,r},cnt(0),lazy(0),has{0,0}{
    if(l){
      cnt+=l->get_cnt();
      has[0]|=l->get_has(0)|(1<<k);
      has[1]|=l->get_has(1);
    }
    if(r){
      cnt+=r->get_cnt();
      has[0]|=r->get_has(0);
      has[1]|=r->get_has(1)|(1<<k);
    }
    assert(has[0]<(1<<(k+1)));
    assert(has[1]<(1<<(k+1)));
  }
  void push(){
    assert(lazy<(1<<(k+1)));
    if(!lazy) return;
    //handle kth bit
    if(lazy&(1<<k)){
      std::swap(chd[0],chd[1]);
      if((has[0]^has[1])&(1<<k)){
	has[0]^=(1<<k);
	has[1]^=(1<<k);
      }
      lazy^=(1<<k);
    }
    //handle rest of bits
    int flip=(has[0]^has[1])&lazy;
    has[0]^=flip;
    has[1]^=flip;
    if(chd[0]) chd[0]->lazy^=lazy;
    if(chd[1]) chd[1]->lazy^=lazy;
    lazy=0;
    assert(has[0]<(1<<(k+1)));
    assert(has[1]<(1<<(k+1)));
  }
};

template<>
struct Trie<-1>{
  int lazy;
  Trie():lazy(0){
  }
  int get_cnt(){
    assert(this!=NULL);
    return 1;
  }
  int get_has(int d){
    assert(this!=NULL);
    return 0;
  }
};

template<int k>
Trie<k>* create(int x){
  if(x&(1<<k)){
    return new Trie<k>(NULL,create<k-1>(x));
  }else{
    return new Trie<k>(create<k-1>(x),NULL);
  }
}
template<>
Trie<-1>* create(int x){
  return new Trie<-1>();
}

template<int k>
std::pair<Trie<k-1>*,Trie<k-1>*> destruct(Trie<k>* a){
  assert(a!=NULL);
  a->push();
  auto res=std::make_pair(a->chd[0],a->chd[1]);
  delete a;
  return res;
}

template<int k>
Trie<k>* join(Trie<k-1>* l,Trie<k-1>* r){
  if(l==NULL&&r==NULL) return NULL;
  return new Trie<k>(l,r);
}

template<int k>
Trie<k>* merge(Trie<k>* a,Trie<k>* b){
  if(!a) return b;
  if(!b) return a;
  auto aa=destruct(a);
  auto bb=destruct(b);
  Trie<k-1>* l=merge<k-1>(aa.first,bb.first);
  Trie<k-1>* r=merge<k-1>(aa.second,bb.second);
  return join<k>(l,r);
}

template<>
Trie<-1>* merge<-1>(Trie<-1>* a,Trie<-1>* b){
  if(!a) return b;
  if(!b) return a;
  delete b;
  return a;
}

template<int k>
//<thres and >=thres
std::pair<Trie<k>*,Trie<k>*> split(Trie<k>* a,int thres){
  if(a==NULL){
    return {NULL,NULL};
  }
  if(thres<=0) return {NULL,a};
  if(thres>=(1<<(k+1))) return {a,NULL};
  assert(k>=0);
  auto aa=destruct(a);
  if(thres<(1<<k)){
    Trie<k-1>* l,*r;
    std::tie(l,r)=split<k-1>(aa.first,thres);
    return std::make_pair(join<k>(l,NULL),join<k>(r,aa.second));
  }else if(thres>(1<<k)){
    Trie<k-1>* l,*r;
    std::tie(l,r)=split<k-1>(aa.second,thres-(1<<k));
    return std::make_pair(join<k>(aa.first,l),join<k>(NULL,r));
  }else{
    return std::make_pair(join<k>(aa.first,NULL),join<k>(NULL,aa.second));
  }
}

template<>
std::pair<Trie<-1>*,Trie<-1>*> split<-1>(Trie<-1>* a,int thres){
  assert(0);
}

template<int k>
Trie<k>* update(Trie<k>* a,int val){
  if(a==NULL) return NULL;
  a->push();
  assert(val<(1<<(k+1)));
  if((val&a->has[0]&a->has[1])==0){
    a->lazy^=(val&a->has[0]);
    return a;
  }
  Trie<k-1>* l,*r;
  std::tie(l,r)=destruct(a);
  l=update<k-1>(l,val&~(1<<k));
  r=update<k-1>(r,val&~(1<<k));
  if(val&(1<<k)){
    return join<k>(NULL,merge<k-1>(l,r));
  }else{
    return join<k>(l,r);
  }
}

template<>
Trie<-1>* update<-1>(Trie<-1>* a,int val){
  return a;
}

int main(){
  Trie<MAXLOGX-1>* root=NULL;
  int N,Q;
  scanf("%d %d",&N,&Q);
  for(int i=0;i<N;i++){
    int A;
    scanf("%d",&A);
    root=merge(root,create<MAXLOGX-1>(A));
  }
  for(int i=0;i<Q;i++){
    int T,L,R;
    scanf("%d %d %d",&T,&L,&R);
    Trie<MAXLOGX-1>* left,*right;
    std::tie(left,root)=split(root,L);
    std::tie(root,right)=split(root,R+1);
    if(T==4){
      printf("%d\n",root?root->cnt:0);
    }else{
      int X;
      scanf("%d",&X);
      if(root!=NULL){
	if(T==1){
	  root->lazy^=((1<<MAXLOGX)-1);
	  root=update(root,X^((1<<MAXLOGX)-1));
	  root->lazy^=((1<<MAXLOGX)-1);
	}else if(T==2){
	  root=update(root,X);
	}else if(T==3){
	  assert(X<(1<<MAXLOGX));
	  root->lazy^=X;
	}
      }
    }
    root=merge(root,left);
    root=merge(root,right);
  }
}

#include <cstdio>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <cassert>

using ll=long long;

const ll INF=1e18+7;

struct Diamond{
  int w,v,t;
  ll a;
}diamonds[200005];
int index[200005];
int N;

struct Node{
  ll sum_w[31];//sum of weights of all diamonds with weight <2^k
  ll sum_v[31];//sum of values of all diamonds with weight <2^k
  ll one_w[31];//sum of weights of light+first heavy when restricted to <2^k
  ll one_v[31];//sum of values of light+first heavy when restricted to <2^k
}st[800005];

void rebuild(int w,int L,int R,int a,int b){
  if(a>=R||b<=L) return;
  if(R-L==1){
    for(int k=1;k<=30;k++){
      st[w].sum_w[k]=diamonds[L].a*diamonds[L].w*(diamonds[L].w<(1<<k));
      st[w].sum_v[k]=diamonds[L].a*diamonds[L].v*(diamonds[L].w<(1<<k));
      st[w].one_w[k]=INF;//query capacity never exceed INF
      st[w].one_v[k]=INF;
      if(diamonds[L].w>=(1<<(k-1))&&diamonds[L].w<(1<<k)&&diamonds[L].a>0){
	st[w].one_w[k]=diamonds[L].w;
	st[w].one_v[k]=diamonds[L].v;
      }
    }
  }else{
    int M=(L+R)/2;
    rebuild(w*2+1,L,M,a,b);
    rebuild(w*2+2,M,R,a,b);
    for(int k=1;k<=30;k++){
      st[w].sum_w[k]=st[w*2+1].sum_w[k]+st[w*2+2].sum_w[k];
      st[w].sum_v[k]=st[w*2+1].sum_v[k]+st[w*2+2].sum_v[k];
      if(st[w*2+1].one_w[k]<st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k]){
	st[w].one_w[k]=st[w*2+1].one_w[k];
	st[w].one_v[k]=st[w*2+1].one_v[k];
      }else{
	st[w].one_w[k]=st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k];
	st[w].one_v[k]=st[w*2+1].sum_v[k-1]+st[w*2+2].one_v[k];
      }
    }
  }
}

//only consider weights <2^k
//take maximal prefix possible
void query_all(int w,int L,int R,int& i,int k,ll& cap,ll& value){
  assert(i>=L&&i<=R);
  assert(R-L>0);
  if(i==R) return;
  if(i==L&&st[w].sum_w[k]<=cap){
    cap-=st[w].sum_w[k];
    value+=st[w].sum_v[k];
    i=R;
  }else if(R-L>1){
    int M=(L+R)/2;
    if(i<M){
      query_all(w*2+1,L,M,i,k,cap,value);
    }
    if(i>=M){
      query_all(w*2+2,M,R,i,k,cap,value);
    }
  }
}

std::array<ll,2> query_one_range_simpl(int w,int L,int R,int a,int b,int k){
  if(a>=R||b<=L) return {INF,0};
  if(a<=L&&b>=R){
    return {st[w].one_w[k],st[w].sum_w[k-1]};
  }else{
    int M=(L+R)/2;
    std::array<ll,2> lsum,rsum;
    lsum=query_one_range_simpl(w*2+1,L,M,a,b,k);
    rsum=query_one_range_simpl(w*2+2,M,R,a,b,k);
    if(lsum[0]<lsum[1]+rsum[0]){
      return {lsum[0],lsum[1]+rsum[1]};
    }else{
      return {lsum[1]+rsum[0],lsum[1]+rsum[1]};
    }
  }
}

std::array<ll,4> query_one_range(int w,int L,int R,int a,int b,int k){
  if(a>=R||b<=L) return {INF,INF,0,0};
  if(a<=L&&b>=R){
    return {st[w].one_w[k],st[w].one_v[k],st[w].sum_w[k-1],st[w].sum_v[k-1]};
  }else{
    int M=(L+R)/2;
    std::array<ll,4> lsum,rsum;
    lsum=query_one_range(w*2+1,L,M,a,b,k);
    rsum=query_one_range(w*2+2,M,R,a,b,k);
    if(lsum[0]<lsum[2]+rsum[0]){
      return {lsum[0],lsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
    }else{
      return {lsum[2]+rsum[0],lsum[3]+rsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
    }
  }
}

//returns min j such that one_w[i..j) <= cap, or -1 if none exist
//reduce cap by weight of light in [max(i,L),R)
int query_one_range_search_(int w,int L,int R,int& i,int k,ll& cap){
  assert(i>=L&&i<=R);
  assert(R-L>0);
  if(i==R) return -1;
  if(i==L&&st[w].one_w[k]>cap){
    cap-=st[w].sum_w[k-1];
    i=R;
    return -1;
  }else if(R-L==1){
    assert(i==L);
    assert(st[w].one_w[k]<=cap);
    cap-=st[w].sum_w[k-1];
    i=R;
    return R;
  }else{
    int M=(L+R)/2;
    int res=-1;
    if(i<M){
      res=query_one_range_search_(w*2+1,L,M,i,k,cap);
    }
    if(res!=-1) return res;
    if(i>=M){
      res=query_one_range_search_(w*2+2,M,R,i,k,cap);
    }
    return res;
  }
}

int query_one_range_search(int i,int k,ll cap){
  //note this copy of cap will be modified
  return query_one_range_search_(0,0,N,i,k,cap);
}

void query_one(int& L,int k,ll& cap,ll& value){
  int high=query_one_range_search(L,k,cap);
  //v[high]<=cap
  if(high!=-1){
    auto v=query_one_range(0,0,N,L,high,k);
    L=high;
    cap-=v[0];
    value+=v[1];
  }
}

ll query(ll cap){
  ll value=0;
  int i=0;
  for(int k=30;k>0;k--){
    query_all(0,0,N,i,k,cap,value);
    if(i==N) break;
    ll take=std::min(diamonds[i].a,cap/diamonds[i].w);
    cap-=take*diamonds[i].w;
    value+=take*diamonds[i].v;
    i++;
    query_one(i,k,cap,value);
  }
  return value;
}

int main(){
  int Q;
  scanf("%d %d",&N,&Q);
  for(int i=0;i<N;i++){
    scanf("%lld %d %d",&diamonds[i].a,&diamonds[i].w,&diamonds[i].v);
    diamonds[i].t=i;
  }
  std::sort(diamonds,diamonds+N,[](Diamond x,Diamond y){
      return (x.v!=y.v)?(x.v>y.v):(x.w<y.w);
    });
  for(int i=0;i<N;i++){
    index[diamonds[i].t]=i;
  }
  rebuild(0,0,N,0,N);
  for(int i=0;i<Q;i++){
    int T;
    scanf("%d",&T);
    if(T==1){
      int K,D;
      scanf("%d %d",&K,&D);
      D--;
      diamonds[index[D]].a+=K;
      rebuild(0,0,N,index[D],index[D]+1);
    }else if(T==2){
      int K,D;
      scanf("%d %d",&K,&D);
      D--;
      diamonds[index[D]].a-=K;
      assert(diamonds[index[D]].a>=0);
      rebuild(0,0,N,index[D],index[D]+1);
    }else{
      ll C;
      scanf("%lld",&C);
      printf("%lld\n",query(C));
    }
  }
}

#include <bits/stdc++.h>
using namespace std;

void solve(){
  int N;
  cin>>N;
  //note: 1<<X means 2^X
  //we put largest coin in first pile
  int sum1=(1<<N), sum2=0;
  //we put n/2-1 smallest coins in first pile
  for (int i=1;i<N/2;i++)
    sum1+=(1<<i);
  //we put remaining n/2 coins in second pile
  for (int i=N/2;i<N;i++)
    sum2+=(1<<i);
  cout<<sum1-sum2<<endl;
}

int main(){
  int t; cin>>t;
  while (t--)
    solve();
}

#include <bits/stdc++.h>
using namespace std;

void solve(){
  int N,K;
  cin>>N>>K;
  set<int>s;
  for (int i=0;i<N;i++){
    int a;
    cin>>a;
    s.insert(a);
  }
  //if more than K distinct numbers, print -1
  if (s.size()>K){
    cout<<-1<<endl;
    return;
  }
  cout<<N*K<<endl;
  for (int i=0;i<N;i++){
    //print the distinct numbers
    for (int b:s)
      cout<<b<<' ';
    //print the extra 1s
    for (int j=0;j<K-(int)s.size();j++)
      cout<<1<<' ';
  }
  cout<<endl;
}

int main(){
  int t; cin>>t;
  while (t--)
    solve();
}

#include <bits/stdc++.h>
using namespace std;

void solve(){
  int n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  sort(s.begin(),s.end());
  //if smallest k letters are not all the same, answer is kth smallest letter
  if (s[0]!=s[k-1]){
    cout<<s[k-1]<<endl;
    return;
  }
  cout<<s[0];
  //if remaining letters aren't the same, we append remaining letters to answer
  if (s[k]!=s[n-1]){
    for (int i=k;i<n;i++)
      cout<<s[i];
  }
  else{
    //remaining letters are the same, so we distribute evenly
    for (int i=0;i<(n-k+k-1)/k;i++)
      cout<<s[n-1];
  }
  cout<<endl;
}

int main(){
  int t; cin>>t;
  while (t--)
    solve();
}

#include <bits/stdc++.h>
using namespace std;

void solve(){
  vector<int>inc;   
  int N;
  cin>>N;
  //construct sequence 1, 2, 4, ... while sum <= N
  for (int i=1;i<=N;i*=2){
    inc.push_back(i);
    N-=i;
  }
  //if sum is not N, we insert and sort
  if (N>0){
    inc.push_back(N);
    sort(inc.begin(),inc.end());
  }
  cout<<inc.size()-1<<endl;
  for (int i=1;i<(int)inc.size();i++)
    cout<<inc[i]-inc[i-1]<<' ';
  cout<<endl;
}

int main(){
  int t; cin>>t;
  while (t--)
    solve();
}

//Solution 1
#include <bits/stdc++.h>
using namespace std;

int N,K;
int a[505],b[505];
bool dp[505][505];  //number of shrubs considered, "extra" red berries

int main(){
  cin>>N>>K;
  long long totA=0,totB=0;
  for (int i=1;i<=N;i++){
    cin>>a[i]>>b[i];
    totA+=a[i];
    totB+=b[i];
  }
  dp[0][0]=true;
  for (int i=1;i<=N;i++){
    for (int j=0;j<K;j++){
      //leave a[i]%K extra red berries
      dp[i][j]=dp[i-1][(j-a[i]%K+K)%K];
      for (int l=0;l<=min(K-1,a[i]);l++){
	//check if we can leave l extra red berries
	if ((a[i]-l)%K+b[i]>=K)
	  dp[i][j]|=dp[i-1][(j-l+K)%K];
      }
    }
  }
  long long ans=0;
  for (int i=0;i<K;i++){
    if (dp[N][i])
      ans=max(ans,(totA+totB-i)/K);
  }
  cout<<ans<<endl;
}

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9+7;
 
int as[200005], bs[200005];
         
vector<pair<int,int> > start[200005];
int ans[200005];
int where[200005];
int N;
         
void show(){
  for(int i=1;i<=N;i++)
    cout<<ans[i]<<' ';
  cout<<endl;
}
 
pair<int,int> st[400005];
 
int query(int l,int r){
  l--;
  pair<int,int> res{INF,INF};
  for(l+=N,r+=N;l<r;l>>=1,r>>=1){
    if(l&1) res=min(res,st[l++]);
    if(r&1) res=min(res,st[--r]);
  }
  return res.second;
}
         
int main(){
  cin>>N; 
  for(int i=1;i<=N;i++){
    cin>>as[i]>>bs[i];
    start[as[i]].push_back({bs[i],i});
  }
  set<pair<int,int> > active;//(right,index)
  for(int i=1;i<=N;i++){
    active.insert(start[i].begin(),start[i].end());
    ans[active.begin()->second]=i;
    where[i]=active.begin()->second;
    active.erase(active.begin());
  }
  for(int i=0;i<N;i++){
    st[i+N]={as[where[i+1]],i+1};
  }
  for(int i=N-1;i>0;i--){
    st[i]=min(st[i<<1],st[i<<1|1]);
  }
  for(int i=1;i<=N;i++){
    int j=query(i+1,bs[where[i]]);
    if(j==INF) continue;
    if(as[where[j]]<=i){
      cout<<"NO"<<endl;
      show();
      swap(ans[where[i]],ans[where[j]]);
      show();
      return 0;
    }
  }
  cout<<"YES"<<endl;
  show();
}

#include <bits/stdc++.h>
using namespace std;

int N;
int a[200005],b[200005];
int label[200005]; //the label of the person at i-th position in our perfect matching
int label2[200005]; //which position the i-th person is at

void perfectMatch(){ //finds a perfect matching
  deque<pair<pair<int,int>,int>>v;
  for (int i=1;i<=N;i++)
    v.push_back({{a[i],b[i]},i});
  sort(v.begin(),v.end());
  multiset<pair<int,int>>mst;
  for (int i=1;i<=N;i++){
    while ((int)v.size()>0 && v[0].first.first<=i){
      mst.insert({v[0].first.second,v[0].second});
      v.pop_front();
    }
    //match person with label to earliest ending interval
    label2[i]=mst.begin()->second;
    label[mst.begin()->second]=i;
    mst.erase(mst.find(*mst.begin()));
  }
}

set<int>active;
int vis[200005];
int from[200005];
int ans[200005];

void foundAnother(int node, int nextNode){
  vector<int>v;
  int cur=node;
  //backtracks on cycle to find other ordering
  while (cur!=label2[nextNode]){
    v.push_back(cur);
    cur=from[cur];
  }
  reverse(v.begin(),v.end());
  v.push_back(label2[nextNode]);
  reverse(v.begin(),v.end());
  cout<<"NO"<<endl;
  for (int i=1;i<=N;i++)
    cout<<label[i]<<' ';
  cout<<endl;
  for (int i=1;i<=N;i++)
    ans[i]=label[i];
  int temp=ans[v.back()];
  for (int i=0;i<(int)v.size();i++)
    swap(temp,ans[v[i]]);
  for (int i=1;i<=N;i++)
    cout<<ans[i]<<' ';
  cout<<endl;
  exit(0);
}
  
void dfs(int node){
  //activates node
  vis[node]=1;
  queue<int>toRemove;
  for (;;){
    //binary search for unvisisited neighbor
    auto it=active.lower_bound(a[node]);
    if (it!=active.end() && *it==label[node]){
      toRemove.push(*it);
      it++;
    }
    if (it==active.end() || *it>b[node])
      break;
    if (vis[label2[*it]]==1) //found cycle (another ordering)
      foundAnother(node,*it);
    toRemove.push(*it);
    if (vis[label2[*it]]==2)
      continue;
    from[label2[*it]]=node;
    dfs(label2[*it]);
  }
  //removes visited nodes from set
  while (!toRemove.empty()){
    if (active.count(toRemove.front()))
      active.erase(toRemove.front());
    toRemove.pop();
  }
  //deactivates and retire node
  vis[node]=2;
}

int main(){
  cin>>N;
  for (int i=1;i<=N;i++)
    cin>>a[i]>>b[i];
  perfectMatch();
  for (int i=1;i<=N;i++)
    active.insert(i);
  for (int i=1;i<=N;i++)
    if (vis[i]==0)
      dfs(i);
  cout<<"YES"<<endl;
  for (int i=1;i<=N;i++)
    cout<<label[i]<<' ';
  cout<<endl;
}

#include <iostream>
using namespace std;

int N,D,a[105];

int main(){
  int T; cin>>T;
  while (T--){
    cin>>N>>D;
    for (int i=1;i<=N;i++)
      cin>>a[i];
    while (D--){ //loop over D days
      for (int i=2;i<=N;i++)
	if (a[i]>0){ //move closest haybale over
	  a[i]--;
	  a[i-1]++;
	  break;
	}
    }
    cout<<a[1]<<endl;
  }
}

#include <iostream>
using namespace std;

int N,D,a[105],ans;

int main(){
  int T; cin>>T;
  while (T--){
    cin>>N>>D;
    for (int i=1;i<=N;i++)
      cin>>a[i];
    for (int i=2;i<=N;i++){
      int move=min(a[i],D/(i-1)); //number of haybales we can move from pile i to pile 1
      a[1]+=move; //update pile 1
      D-=move*(i-1); //update remaining days
    }
    cout<<a[1]<<endl;
  }
}

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

set<int>a;
//you don't have to use set, it was just easier for us

int main(){
  int T; cin>>T;
  while (T--){
    int N,X;
    cin>>N>>X;
    int far=0; //largest favorite number
    for (int i=0;i<N;i++){
      int A;
      cin>>A;
      a.insert(A);
      far=max(far,A);
    }
    if (a.count(X)) //X is favorite number
      cout<<1<<endl;
    else
      cout<<max(2,(X+far-1)/far)<<endl; //expression as explained in tutorial
    a.clear();
  }
}

#include <iostream>
using namespace std;

typedef long long ll;
ll arr1[26],arr2[26][26];

int main(){
  string S;
  cin>>S;
  for (int i=0;i<S.length();i++){
    int c=S[i]-'a';
    for (int j=0;j<26;j++)
      arr2[j][c]+=arr1[j];
    arr1[c]++;
  }
  ll ans=0;
  for (int i=0;i<26;i++)
    ans=max(ans,arr1[i]);
  for (int i=0;i<26;i++)
    for (int j=0;j<26;j++)
      ans=max(ans,arr2[i][j]);
  cout<<ans<<endl;
}

#include <cstdio>
#include <vector>
#include <algorithm>

const int INF=1e9+7;

int N;
int as[200005];

std::vector<int> edges[200005];

int dist[2][200005];
int q[200005];

void bfs(int* dist,int s){
  std::fill(dist,dist+N,INF);
  int qh=0,qt=0;
  q[qh++]=s;
  dist[s]=0;
  while(qt<qh){
    int x=q[qt++];
    for(int y:edges[x]){
      if(dist[y]==INF){
	dist[y]=dist[x]+1;
	q[qh++]=y;
      }
    }
  }
}

int main(){
  int M,K;
  scanf("%d %d %d",&N,&M,&K);
  for(int i=0;i<K;i++){
    scanf("%d",&as[i]);
    as[i]--;
  }
  std::sort(as,as+K);
  for(int i=0;i<M;i++){
    int X,Y;
    scanf("%d %d",&X,&Y);
    X--,Y--;
    edges[X].push_back(Y);
    edges[Y].push_back(X);
  }
  bfs(dist[0],0);
  bfs(dist[1],N-1);
  std::vector<std::pair<int,int> > data;
  for(int i=0;i<K;i++){
    data.emplace_back(dist[0][as[i]]-dist[1][as[i]],as[i]);
  }
  std::sort(data.begin(),data.end());
  int best=0;
  int max=-INF;
  for(auto it:data){
    int a=it.second;
    best=std::max(best,max+dist[1][a]);
    max=std::max(max,dist[0][a]);
  }
  printf("%d\n",std::min(dist[0][N-1],best+1));
}

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>

const int MOD=1e9+7;

int modexp(int base,int exp){
  int ac=1;
  for(;exp;exp>>=1){
    if(exp&1) ac=1LL*ac*base%MOD;
    base=1LL*base*base%MOD;
  }
  return ac;
}

int inverse(int x){
  return modexp(x,MOD-2);
}

int fs[100005];
int left[100005],right[100005];
std::vector<int> cows[100005];//cows[f]: hunger of cows that like flavor f 
int asleep[100005];
int ways[100005];
int total_asleep=0,total_ways=1;

void calc_ways(int f){
  int a=std::upper_bound(cows[f].begin(),cows[f].end(),left[f])-cows[f].begin();
  int b=std::upper_bound(cows[f].begin(),cows[f].end(),right[f])-cows[f].begin();
  if(a>b) std::swap(a,b);
  long long cnt2=1LL*a*b-a;
  int cnt1=a+b;
  cnt2%=MOD;
  if(cnt2>0){
    asleep[f]=2;
    ways[f]=cnt2;
  }else if(cnt1>0){
    asleep[f]=1;
    ways[f]=cnt1;
  }else{
    asleep[f]=0;
    ways[f]=1;
  }
}

//fixed left cow, with hunger left[i]
//precondition: such cow exists
void calc_ways_stuck(int f){
  int b=std::upper_bound(cows[f].begin(),cows[f].end(),right[f])-cows[f].begin();
  if(right[f]>=left[f])
    b--;
  int cnt2=b;
  if(cnt2>0){
    asleep[f]=2;
    ways[f]=cnt2;
  }else{
    asleep[f]=1;
    ways[f]=1;
  }
}

int ans_asleep=0,ans_ways=0;

void add_to_ans(int asleep,int ways){
  if(asleep>ans_asleep){
    ans_asleep=asleep;
    ans_ways=0;
  }
  if(asleep==ans_asleep)
    ans_ways=(ans_ways+ways)%MOD;
}

int main(){
  int N,M;
  scanf("%d %d",&N,&M);
  for(int i=1;i<=N;i++){
    scanf("%d",&fs[i]);
    right[fs[i]]++;
  }
  for(int i=0;i<M;i++){
    int F,H;
    scanf("%d %d",&F,&H);
    cows[F].push_back(H);
  }
  for(int f=1;f<=N;f++)
    std::sort(cows[f].begin(),cows[f].end());
  for(int f=1;f<=N;f++){
    calc_ways(f);
    total_asleep+=asleep[f];
    total_ways=1LL*total_ways*ways[f]%MOD;
  }
  add_to_ans(total_asleep,total_ways);
  for(int i=1;i<=N;i++){
    total_asleep-=asleep[fs[i]];
    total_ways=1LL*total_ways*inverse(ways[fs[i]])%MOD;
    right[fs[i]]--;
    left[fs[i]]++;
    if(std::binary_search(cows[fs[i]].begin(),cows[fs[i]].end(),left[fs[i]])){
      calc_ways_stuck(fs[i]);
      int here_asleep=total_asleep+asleep[fs[i]];
      int here_ways=1LL*total_ways*ways[fs[i]]%MOD;
      add_to_ans(here_asleep,here_ways);
    }
    calc_ways(fs[i]);
    total_asleep+=asleep[fs[i]];
    total_ways=1LL*total_ways*ways[fs[i]]%MOD;
  }
  printf("%d %d\n",ans_asleep,ans_ways);
}

#include <cstdio>
#include <vector>
#include <cassert>
#include <queue>
#include <algorithm>

const int INF=1e9+7;

std::vector<int> edges[400005];

int anc[19][400005];
int depth[400005];

void dfs(int node){
  for(int child:edges[node]){
    edges[child].erase(std::find(edges[child].begin(),edges[child].end(),node));
    anc[0][child]=node;
    for(int k=1;k<19;k++){
      anc[k][child]=anc[k-1][anc[k-1][child]];
    }
    depth[child]=depth[node]+1;
    dfs(child);
  }
}

int la(int node,int len){
  for(int k=19-1;k>=0;k--){
    if(len&(1<<k)){
      node=anc[k][node];
    }
  }
  return node;
}

int lca(int a,int b){
  if(depth[a]<depth[b]) std::swap(a,b);
  a=la(a,depth[a]-depth[b]);
  if(a==b) return a;
  for(int k=19-1;k>=0;k--){
    if(anc[k][a]!=anc[k][b]){
      a=anc[k][a];
      b=anc[k][b];
    }
  }
  return anc[0][a];
}

//move x steps from a to b
//assumes x<=dist(a,b)
int walk(int a,int b,int x){
  int c=lca(a,b);
  if(x<=depth[a]-depth[c]){
    return la(a,x);
  }
  int excess=x-(depth[a]-depth[c]);
  assert(excess<=(depth[b]-depth[c]));
  return la(b,depth[b]-depth[c]-excess);
}

int uf[400005];
int dist[400005];//dist[x]=0 iff x is rest stop

int find(int a){
  while(a!=uf[a]){
    a=uf[a]=uf[uf[a]];
  }
  return a;
}

bool query(int K){
  int A,B;
  scanf("%d %d",&A,&B);
  A--,B--;
  int C=lca(A,B);
  if(depth[A]+depth[B]-2*depth[C]<=2*K){
    return true;
  }else{
    return find(walk(A,B,K))==find(walk(B,A,K));
  }
}

int main(){
  int N,K,R;
  scanf("%d %d %d",&N,&K,&R);
  int oldN=N;
  for(int i=0;i<oldN-1;i++){
    int X,Y;
    scanf("%d %d",&X,&Y);
    X--,Y--;
    edges[X].push_back(N);
    edges[N].push_back(X);
    edges[Y].push_back(N);
    edges[N].push_back(Y);
    N++;
  }
  for(int i=0;i<N;i++){
    uf[i]=i;
  }
  std::fill(dist,dist+N,INF);
  std::queue<int> frontier;
  for(int i=0;i<R;i++){
    int X;
    scanf("%d",&X);
    X--;
    dist[X]=0;
    frontier.push(X);
  }
  while(!frontier.empty()){
    int x=frontier.front();
    if(dist[x]>K-1) break;
    frontier.pop();
    for(int y:edges[x]){
      uf[find(y)]=find(x);
      if(dist[y]==INF){
	dist[y]=dist[x]+1;
	frontier.push(y);
      }
    }
  }
  dfs(0);
  int V;
  scanf("%d",&V);
  while(V--){
    if(query(K)){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
}

#include <cstdio>
#include <queue>
#include <vector>
#include <stdint.h>
#include <algorithm>

const long long INF=1e9+7;

const long long MAXV=50;
const long long MAXE=MAXV*(MAXV-1);

long long SRC,SNK;

long long elist[MAXE*2];
long long next[MAXE*2];
long long head[MAXV];
long long cap[MAXE*2];
long long cost[MAXE*2];
long long tot=0;

void add(long long x,long long c,long long w){
  elist[tot]=x;
  cap[tot]=c;
  cost[tot]=w;
  next[tot]=head[x];
  head[x]=tot++;
}

long long dist[MAXV];
long long prev[MAXV];
std::queue<long long> q;

long long total_cost=0;
long long total_flow=0;

int main(){
  long long N,M;
  scanf("%lld %lld",&N,&M);
  SRC=0,SNK=N-1;
  std::fill(head,head+N,-1);
  for(long long i=0;i<M;i++){
    long long A,B,C;
    scanf("%lld %lld %lld",&A,&B,&C);
    A--,B--;
    add(A,1,C);
    add(B,0,-C);
  }
  std::vector<std::pair<long long,long long> > crit;
  crit.push_back({0,0});
  while(true){
    std::fill(dist,dist+N,INF);
    dist[SRC]=0;
    prev[SRC]=-1;
    q.push(SRC);
    while(!q.empty()){
      long long node=q.front();
      q.pop();
      for(long long e=head[node];e!=-1;e=next[e]){
	long long i=elist[e^1];
	if(cap[e]){
	  if(dist[i]>dist[node]+cost[e]){
	    dist[i]=dist[node]+cost[e];
	    prev[i]=e;
	    q.push(i);
	  }
	}
      }
    }
    crit.push_back({1LL*total_flow*dist[SNK]-total_cost,dist[SNK]});
    if(dist[SNK]==INF) break;
    long long aug=INF;
    for(long long x=SNK;x!=SRC;x=elist[prev[x]]){
      aug=std::min(aug,cap[prev[x]]);
    }
    for(long long x=SNK;x!=SRC;x=elist[prev[x]]){
      cap[prev[x]]-=aug;
      cap[prev[x]^1]+=aug;
    }
    total_flow+=aug;
    total_cost+=1LL*dist[SNK]*aug;
  }
  long long Q;
  scanf("%lld",&Q);
  while(Q--){
    long long X;
    scanf("%lld",&X);
    auto it=std::lower_bound(crit.begin(),crit.end(),std::pair<long long,long long>{X+1,0});
    double D=(long double)((X-(it-1)->first)*it->second+(it->first-X)*((it-1)->second))/(it->first-(it-1)->first);
    printf("%.10lf\n",D);
  }
  return 0;
}