int bag_01() { //01背包     for(int i = 1; i <= n; i++)        for(int j = c; j >= w[i]; j--)            f[j] = max(f[j], f[j-w[i]]+v[i]);    return f[c];}//对于完全背包（物品不限）：将第二个循环的顺序反向即可。 

//这是找最大int Binary_Search(int Left, int Right) {    while(Left <= Right) {        int Mid = (Left + Right) / 2;        if(check(Mid))            Left = Mid + 1;        else            Right = Mid - 1;    }    return Left - 1;}//这是找最小int Binary_Search(int Left, int Right) {    while(Left <= Right) {        int Mid = (Left + Right) / 2;        if(check(Mid))            Right = Mid - 1;        else            Left = Mid + 1;    }    return Right + 1;}

int calc(int n){ //calc(n) : 计算n的因子个数     int ans=1, t;    for (int i=2; i*i<=n; i++){        for (t=0; n%i==0; n/=i)            t++;        ans*=t+1;    }    if (n>1)         ans*=2;    return ans;}

int gcd(int a, int b) {    return b ? gcd(b, a%b) : a; }//gcd函数返回a和b的最大公约数（a>b) 最小公倍数=a*b/gcd(a,b) 

int LCS() {    for(int i = 1; i <= xl; i++)         for(int j = 1; j <= yl; j++)            if(x[i] == y[j])                 f[i%2][j] = f[(i-1)%2][j-1]+1;            else                f[i%2][j]=max(f[(i-1)%2][j],f[i%2][j-1]);    return f[xl%2][yl];}

void prime(int n) { //筛法求素数表     for(int i = 2; i <= sqrt(n); i++)        if(!p[i])            for(int j = i+i; j <= n; j += i) p[j] = 1;}//p[i]=0：该数是素数；p[i]=1：该数不是素数 

int quickpow(int a, int b, int m){ //快速幂 求a^b%m的值         int t=1;    while (b){        if (b&1) t=t*a%m;        b>>=1; a=a*a%m;      }    return t;}

inline void read(int& x){    char c=getchar(); int f=1,num=0;    for(;c<‘0‘||c>‘9‘;c=getchar()) if(c==‘-‘)f=-1;    for(;c>=‘0‘&&c<=‘9‘;c=getchar()) num=num*10+c-‘0‘;    x=num*f;}