问题标题: 送3200经验

#include <bits/stdc++.h>
using namespace std;
const int M = 15;
const int N = 500005;
const int MOD = 1e9+7;
#define int long long
int read(){
    int x=0,f=1;
    char c;
    while((c=getchar())<'0' || c>'9'){
        if(c=='-') f=-1;
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
int n,k,inv[M],s[M][M],w[M],a[M],dt[M];
int ans,c[N],d[N],l[M],r[M],z[M];
int Abs(int x){
    if(x>0){
        return x;
    }
    return -x;
}
int walk(int x,int y){
    z[x]+=y;
    if(l[x]>z[x] || r[x]<z[x]){
        l[x]=min(l[x],z[x]);
        r[x]=max(r[x],z[x]);
        return 1;
    }
    return 0;
}
void init(int k){
    s[0][0]=inv[0]=inv[1]=1;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            s[i][j]=(s[i-1][j-1]+s[i-1][j]*j)%MOD;
        }
    }
    for(int i=2;i<=k+1;i++){
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
}
int cal(int k,int n)
{
    int sum=0,C=1;
    for(int i=0;i<=k;i++){
        C=C*max(0ll,n-i)%MOD;
        sum=(sum+C*inv[i+1]%MOD*s[k][i])%MOD;
    }
    return sum;
}
int work()
{
    int lim=MOD,res=0;
    for(int i=1;i<=k;i++){
        if(dt[i]) lim=min(lim,(a[i]+dt[i]-1)/dt[i]);
    }
    int dp[M]={1};
    for(int i=1;i<=k;i++){
        for(int j=i;j>=0;j--)
        {
            dp[j+1]=(dp[j+1]-dt[i]*dp[j])%MOD;
            dp[j]=dp[j]*a[i]%MOD;
        }
    }
    for(int i=0;i<=k;i++){
        res=(res+dp[i]*cal(i,lim))%MOD;
    }
    return res;
}
signed main()
{
    n=read();k=read();
    init(k);
    for(int i=1;i<=k;i++){
        w[i]=read();
    }
    for(int i=1;i<=n;i++){
        c[i]=read();d[i]=read();
        if(walk(c[i],d[i]) && r[c[i]]-l[c[i]]<=w[c[i]])
        {
            int x=1;
            for(int j=1;j<=k;j++)
                if(j!=c[i])
                    x=(x*max(0ll,w[j]-r[j]+l[j]))%MOD;
            ans=(ans+i*x)%MOD;
        }
    }
    int fl=1;
    for(int i=1;i<=k;i++)
    {
        fl&=(z[i]==0);
        dt[i]=Abs(z[i]);
    }
    if(fl==1)
    {
        for(int i=1;i<=k;i++)
            fl|=(r[i]-l[i]>=w[i]);
        if(fl) puts("-1");
        else printf("%lld\n",ans);
        return 0;
    }
    for(int i=1;i<=k;i++)
        a[i]=max(0ll,w[i]-r[i]+l[i]);
    ans=(ans+n*work())%MOD;
    for(int i=1;i<=n;i++)
        if(walk(c[i],d[i]) && r[c[i]]-l[c[i]]<=w[c[i]])
        {
            fl=1;
            for(int j=1;j<=k;j++)
                if(j!=c[i])
                    fl&=(w[j]-r[j]+l[j]>0);
            if(!fl) continue;
            for(int j=0;j<k;j++)
                if(j!=c[i]) a[j]=max(0ll,w[j]-r[j]+l[j]);
            a[c[i]]=w[c[i]]-r[c[i]]+l[c[i]]+1;
            ans=(ans+i*work())%MOD;
            a[c[i]]=w[c[i]]-r[c[i]]+l[c[i]];
            ans=(ans-i*work())%MOD;
        }
    printf("%lld\n",(ans+MOD)%MOD);
}