#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=8*123;
int dp[maxn][maxn];
int n;
struct he
{
    int id, x,y;
} Sky[maxn];
bool cmp(he a,he b)
{
    return a.y>b.y;
}
void init()
{   scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&Sky[i].x,&Sky[i].y);
        Sky[i].id=i;
    }
    sort(Sky+1,Sky+1+n,cmp);
}
void play()
{
    dp[1][0]=0;
    for(int i=2; i<=n; i++)
    {
        int x=Sky[i].x;
        int y=Sky[i].y;
        for(int j=1; j<i; j++)
        {
            int le=j;
            int ri=i-j-1;
            if(le<ri)continue;
            dp[le+1][ri]=dp[le][ri];
        }
        for(int j=1; j<i; j++)
        {
            int le=j;
            int ri=i-j-1;
            if(le<=ri)continue;
            dp[le][ri+1]=max(dp[le][ri]+x,dp[le][ri+1]);
        }
    }
    printf("%d\n",dp[n/2][n/2]);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//   cout << "Hello world!" << endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=12345678;
bool notPrime[maxn];
int ai[123456];
struct he
{
    int l,r,lazy,ans;
} Sky[123456*4];
void BuildTree(int l,int r,int now)
{
    Sky[now].l=l;
    Sky[now].r=r;
    Sky[now].lazy=0;
    Sky[now].ans=0;
    if(l==r)
    {
        Sky[now].lazy=ai[l];
        if(!notPrime[Sky[now].lazy])Sky[now].ans=1;
        else Sky[now].ans=0;
        return;
    }
    int mid=(l+r)>>1;
    BuildTree(l,mid,now<<1);
    BuildTree(mid+1,r,now<<1|1);
    Sky[now].ans=Sky[now<<1].ans+Sky[now<<1|1].ans;
}

void PushDown(int x)
{
    if(Sky[x].lazy==0)return;
    int ls=x<<1;
    int rs=x<<1|1;
    if(!notPrime[Sky[x].lazy])
    {
        Sky[ls].ans=Sky[ls].r-Sky[ls].l+1;
        Sky[rs].ans=Sky[rs].r-Sky[rs].l+1;
    }
    else
    {
        Sky[ls].ans=0;
        Sky[rs].ans=0;
    }
    Sky[ls].lazy=Sky[x].lazy;
    Sky[rs].lazy=Sky[x].lazy;
    Sky[x].lazy=0;
}//单点
void Update1(int id,int v,int now)
{
    if(Sky[now].l==id&&Sky[now].r==id)
    {
        Sky[now].lazy+=v;
        if(!notPrime[Sky[now].lazy])Sky[now].ans=1;
        else Sky[now].ans=0;
        return;
    }
    PushDown(now);
    int mid=(Sky[now].l+Sky[now].r)>>1;
    if(id<=mid)
    {
        Update1(id,v,now<<1);
    }
    else
    {
        Update1(id,v,now<<1|1);
    }
    Sky[now].ans=Sky[now<<1].ans+Sky[now<<1|1].ans;
}
//区间
void Update2(int l,int r,int now,int v)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {
        Sky[now].lazy=v;
        if(!notPrime[v])
        {
            Sky[now].ans=r-l+1;
        }
        else
        {
            Sky[now].ans=0;
        }
        return;
    }
    PushDown(now);
    int mid=(Sky[now].l+Sky[now].r)>>1;
    if(r<=mid)
    {
        Update2(l,r,now<<1,v);
    }
    else if(l>mid)
    {
        Update2(l,r,now<<1|1,v);
    }
    else
    {
        Update2(l,mid,now<<1,v);
        Update2(mid+1,r,now<<1|1,v);
    }
    Sky[now].ans=Sky[now<<1].ans+Sky[now<<1|1].ans;
}
int  Query(int l,int r,int now)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {

        return Sky[now].ans;
    }
    PushDown(now);
    int mid=(Sky[now].l+Sky[now].r)>>1;
    int o1=0,o2=0;
    if(r<=mid)
    {
        o1=Query(l,r,now<<1);
    }
    else if(l>mid)
    {
        o2=Query(l,r,now<<1|1);
    }
    else
    {
        o1=Query(l,mid,now<<1);
        o2=Query(mid+1,r,now<<1|1);
    }
    return o1+o2;
}
int T,N,Q;
char OP[10];
void init()
{
    scanf("%d%d",&N,&Q);
    for(int i=1; i<=N; i++)
    {
        scanf("%d",&ai[i]);

    }
    BuildTree(1,N,1);
}
void play()
{
    int l,r,v;
    while(Q--)
    {
        scanf("%s",OP+1);
        scanf("%d%d",&v,&l);
        if(OP[1]=='A')
        {
            Update1(l,v,1);
        }
        else if(OP[1]=='R')
        {
            scanf("%d",&r);
            Update2(l,r,1,v);
        }
        else
        {
            int ans=Query(v,l,1);
            printf("%d\n",ans);
        }
    }
}
int main()
{
    memset(notPrime,0,sizeof(notPrime));
    notPrime[1]=1;
    for(int i = 2; i*i <= maxn; i++)
    {
        if(!notPrime[i])
        {
            for(int j = i*i; j <= maxn; j += i)
            {
                notPrime[j] = true;
            }
        }
    }
    scanf("%d",&T);

    while(T--)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

退役啦~  还是回来好好做题了。即使到最后一无所有。我至少没放弃我曾经想要的生活。 Update 2015-10-24

/*
Author:Chieh
Because Of Coding
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct matrix
{
    int e[26][26];
};
matrix Cal(matrix p,matrix q,int len)
{
    matrix c;
    for(int i=1; i<=len; i++)
    {
        for(int j=1; j<=len; j++)
        {
            c.e[i][j]=0;
            for(int k=1; k<=len; k++)
            {
                c.e[i][j]=c.e[i][j]+p.e[i][k]*q.e[k][j];
            }
            c.e[i][j]=min(1,c.e[i][j]);
        }
    }
    return c;
}
int can[6][6];
int T;
char ch[123];
int n,m;
bool dist[30][30];
matrix s,a;
void init()
{
    memset(dist,0,sizeof(dist));
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%s",ch+1);
            int u=can[i][j];
            int len=strlen(ch+1);
            int o1=-1,o2=-1;
            for(int k=1; k<=len; k++)
            {
                if(ch[k]>='1'&&ch[k]<='5')
                {
                    if(o1==-1)o1=ch[k]-'0';
                    else
                    {
                        o2=ch[k]-'0';
                        int v=can[o1][o2];
                        dist[u][v]=1;
                        o1=-1;
                        o2=-1;
                    }
                }
            }
        }
    }

}
void exp_pow(int b)
{
    while(b)
    {
        if(b&1)s=Cal(s,a,25);
        a=Cal(a,a,25);
        b>>=1;
    }
}
int ai[30];
int bi[30];
void play()
{

    int q,t;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&t);
        for(int i=1; i<=25; i++)
        {
            for(int j=1; j<=25; j++)
            {
                a.e[i][j]=0;
                if(i==j)s.e[i][j]=1;
                else s.e[i][j]=0;
                if(i==can[n][m])continue;
                if(dist[i][j]==1)
                {
                    a.e[i][j]=1;
                }
            }
        }
        exp_pow(t);
        int sum=0;
        bool flag=0;
        for(int j=1; j<=25; j++)
        {
            int tm=0;
            for(int k=1; k<=25; k++)
            {
                tm=tm+ai[k]*s.e[k][j];
            }
            tm=min(tm,1);
            if(tm)sum++;
            if(j==can[n][m]&&tm)flag=1;
        }
        if(flag&&sum>1)printf("Maybe\n");
        else if(flag&&sum==1)printf("True\n");
        else printf("False\n");
    }
}
int main()
{
    memset(ai,0,sizeof(ai));
    ai[1]=1;
    int st=0;

    for(int i=1; i<=5; i++)
    {
        for(int j=1; j<=5; j++)
        {
            can[i][j]=++st;
        }
    }
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
        printf("\n");
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
//dp[i]=dp[i-1]*m-s;s=dp[i-1]-s; 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct matrix
{
   LL e[2][2];
};
matrix Cal(matrix p,matrix q,int len,int MOD)
{
    matrix c;
    for(int i=0; i<len; i++)
    {
        for(int j=0; j<len; j++)
        {
            c.e[i][j]=0;
            for(int k=0; k<len; k++)
            {
                c.e[i][j]=(c.e[i][j]+((p.e[i][k]*q.e[k][j])%MOD))%MOD;
            }
        }
    }
    return c;
}
const int MOD=1000000007;
int n,m,k;
matrix a,s;
void init()
{
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            if(i==j)s.e[i][j]=1;
            else s.e[i][j]=0;
        }
    }
    a.e[0][0]=m;
    a.e[0][1]=1;
    a.e[1][0]=-k;
    a.e[1][1]=-1;
}
void exp_pow(int b)
{
    while(b)
    {
        if(b&1)s=Cal(s,a,2,MOD);
        a=Cal(a,a,2,MOD);
        b>>=1;
    }
}
void play()
{
    exp_pow(n);
    LL ans=s.e[0][0];
    while(ans<0)ans+=MOD;
    printf("%lld\n",ans);

}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234567;
int k,M;
int  m[maxn][2];
int f[maxn];
int C[71][31];
void init()
{
    m[0][0]=C[0][M];
    m[0][1]=C[0][M];
    m[1][0]=C[1][M];
    m[1][1]=C[0][M];
    f[1]=C[1][M];
    m[2][0]=C[1][M];
    m[2][1]=C[1][M];
    f[2]=C[2][M];
    for(int i=3; i<=k; i++)
    {
        m[i][0]=C[m[i-1][0]+m[i-1][1]][M];
        m[i][1]=f[i-1];
        f[i]=m[i-2][1];
        f[i]=C[f[i]+C[m[i-2][0]*2][M]][M];
    }
}
void play()
{
    printf("%d\n",(m[k][0]+m[k][1]+f[k])%M);
}
int main()
{
    for(int i=0; i<=70; i++)
    {
        for(int j=1; j<=30; j++)
        {
            C[i][j]=i%j;
        }
    }
    while(scanf("%d%d",&k,&M)!=EOF)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}
/*
Author:Chieh
Because Of Coding
*/
// dp[i]=dp[i-1]+dp[i-3]+dp[i-4]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct matrix
{
    int e[4][4];
 
};
matrix Cal(matrix p,matrix q,int len,int MOD)
{
    matrix c;
    for(int i=0; i<len; i++)
    {
        for(int j=0; j<len; j++)
        {
            c.e[i][j]=0;
            for(int k=0; k<len; k++)
            {
                c.e[i][j]=(c.e[i][j]+(p.e[i][k]*q.e[k][j]%MOD))%MOD;
            }
        }
    }
    return c;
}
int M;
int k;
matrix s,a;
void init()
{
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(i==j)s.e[i][j]=1;
            else s.e[i][j]=0;
            if(i!=1&&j==0)a.e[i][j]=1;
            else if(i+1==j)a.e[i][j]=1;
            else a.e[i][j]=0;
        }
    }
}
void exp_pow(int b)
{
    while(b){
        if(b&1)s=Cal(s,a,4,M);
        a=Cal(a,a,4,M);
        b>>=1;
    }
}
int ai[4];
void play()
{
    if(k<=4)printf("%d\n",ai[k-1]%M);
    else{
        k=k-4;
        exp_pow(k);
        int ans=0;
        for(int i=0;i<4;i++){
            ans=(ans+((ai[3-i]*s.e[i][0])%M))%M;
        }
        printf("%d\n",ans);
    }
}
int main()
{
    ai[0]=2;
    ai[1]=4;
    ai[2]=6;
    ai[3]=9;
    while(scanf("%d%d",&k,&M)!=EOF)
    {
 
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
int k,m;
int F[10];
int d;
struct matrix
{
    LL e[10][10];
};
void init()
{
    d=9;
    for(int i=0; i<=9; i++)
    {
        scanf("%d",&F[i]);
    }
}
matrix mul(matrix p,matrix q)
{
    LL i,j,k;
    matrix c;
    for(i=0; i<=d; i++)
    {
        for(j=0; j<=d; j++)
        {
            c.e[i][j]=0;
            for(k=0; k<=d; k++)
                c.e[i][j]=(c.e[i][j]+p.e[i][k]*q.e[k][j])%m;
        }
    }
    return c;
}
matrix s;
matrix a;
void matrix_pow(LL b)
{
    while(b)
    {
        if(b&1)s=mul(s,a);
        a=mul(a,a);
        b=b>>1;
    }
    //a矩阵的b次 返回 s矩阵
}

void play()
{
    if(k<10)printf("%d\n",k);
    else
    {
        for(int i=0; i<=9; i++)
        {
            for(int j=0; j<=9; j++)
            {
                if(i==j) s.e[i][j]=1;
                else s.e[i][j]=0;
            }
        }
        // cout<<s.e[0][2]<<endl;

        for(int i=0; i<=9; i++)
        {
            for(int j=0; j<=9; j++)
            {
                if(j==0)
                {
                    a.e[i][j]=F[i];
                }
                else if(i+1==j)
                {
                    a.e[i][j]=1;
                }
                else
                {
                    a.e[i][j]=0;
                }
            }
        }
        /*   for(int i=0; i<=9; i++)
           {
               for(int j=0; j<=9; j++)
               {
                   cout<<a.e[i][j]<<" ";
               }
               cout<<endl;
           }
           cout<<"---------------------------"<<endl;*/
        matrix_pow(k-9);
        /*  for(int i=0; i<=9; i++)
          {
              for(int j=0; j<=9; j++)
              {
                  cout<<s.e[i][j]<<" ";
              }
              cout<<endl;
          }*/
        LL ans=0;
        int t=9;
        for(int i=0; i<=9; i++)
        {
            ans=(ans+(t*s.e[i][0])%m)%m;
            t--;
        }
        printf("%I64d\n",ans);
    }
}
int main()
{
    while(scanf("%d%d",&k,&m)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
int len[100000];
int Link[11];
int idx[11];
int  Get(int x,int y)
{

    while(1)
    {
        int ys=x%10;
        x/=10;
        y--;
        if(y==0)return ys;
    }
}
void init()
{

    Link[1]=1;
    int p=2;
    for(int i=2; i<=10; i++)
    {
        Link[i]=Link[i-1]+p;
        p*=2;
        p*=2;
    }
    int st=1;
    int bef=0;
    for(int i=1; i<=99999; i++)
    {
        int t;
        if(i>=10000)t=5;
        else if(i>=1000)t=4;
        else if(i>=100)t=3;
        else if(i>=10)t=2;
        else t=1;
        int now=bef+t;
        if(st<=10&&now>=Link[st])
        {
            int xi=Link[st]-bef;
            idx[st]=Get(i,t-xi+1);
            st++;
        }
        len[i]=idx[st-1];
        bef=now;
    }
}
int n;
void play()
{
    printf("%d\n",len[n]);
}
int main()
{
    init();
    while(scanf("%d",&n)!=EOF){
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=3*123456;
int ai[maxn];
int n,k;
bool cmp(int a,int b)
{
    return a>b;
}
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
    sort(ai+1,ai+1+n,cmp);
}
LL dp[5678][5678];
void play()
{
    if(n%k==0)
    {
        LL sum=0;
        int p=n/k;
        for(int i=1; i<=n; i+=p)
        {
            sum+=ai[i]-ai[i+p-1];
        }
        printf("%I64d\n",sum);
    }
    else
    {

        int ys=n%k;
        int s1=ys;
        int v1=n/k+1;
        int s2=k-ys;
        int v2=n/k;
        for(int i=0; i<=k; i++)
        {
            for(int j=0; j<=k; j++)
            {
                dp[i][j]=1000000000000000000LL;
            }
        }
        dp[0][0]=0;
        for(int i=0;i<=s1;i++){
            for(int j=0;j<=s2;j++){
               int a1=i;
               int a2=j;
               int st=i*v1+j*v2+1;
                if(a1<s1){
                    dp[a1+1][a2]=min(dp[a1+1][a2],dp[a1][a2]+ai[st]-ai[st+v1-1]);
                }
                if(a2<s2){
                    dp[a1][a2+1]=min(dp[a1][a2+1],dp[a1][a2]+ai[st]-ai[st+v2-1]);
                }
            }
        }
        printf("%I64d\n",dp[s1][s2]);
    }
}


int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=5*12;
double  ai[maxn*maxn][maxn][maxn];
int T,n,m;
double ans;
void init()
{
    ans=0;
    scanf("%d%d",&n,&m);
    ai[0][0][0]=1;
    double  p=n*m;
    for(int k=1; k<=n*m; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                ai[k][i][j]=0;
                ai[k][i][j]+=i*j*ai[k-1][i-1][j]/p;
                ai[k][i][j]+=j*i*ai[k-1][i][j-1]/p;
                ai[k][i][j]+=i*j*ai[k-1][i-1][j-1]/p;
                if((i!=n||j!=m)&&i*j>=k)
                {
                    ai[k][i][j]+=ai[k-1][i][j]*(i*j-k+1)/p;
                }
            }
        }
        p--;
    }
}
void play()
{

    double ans=0;
    for(int i=1; i<=n*m; i++)
    {
        ans+=ai[i][n][m]*i;
    }
    printf("%.10f\n",ans);
}

int main()
{

    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}