度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。
度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。
当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。
Input本题包含若干组测试数据。
第一行两个整数n，m,表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<=n<=100000
1<=m<=1000
1<=a[i]<=1000
0<=b[i]<=10
0<=k[i]<=100000
0<=p[i]<=1000
Output对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1
Sample Input 1 2 3 5 7 10 6 8 1 2 3 5 10 7 8 6 Sample Output 6 18 #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <algorithm> using namespace std; #define pi acos(-1) #define endl '\n' #define srand() srand(time(0)); #define me(x,y) memset(x,y,sizeof(x)); #define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++) #define close() ios::sync_with_stdio(0); cin.tie(0); #define FOR(x,n,i) for(int i=x;i<=n;i++) #define FOr(x,n,i) for(int i=x;i<n;i++) #define W while #define sgn(x) ((x) < 0 ? -1 : (x) > 0) #define bug printf("***********\n"); typedef long long LL; const int INF=0x3f3f3f3f; const LL LINF=1e18+7; const int dx[]= {-1,0,1,0,1,-1,-1,1}; const int dy[]= {0,1,0,-1,-1,1,-1,1}; const int maxn=2005; const int maxx=1e5+100; const double EPS=1e-7; const int mod=998244353; template<class T>inline T min(T a,T b,T c) { return min(min(a,b),c); } template<class T>inline T max(T a,T b,T c) { return max(max(a,b),c); } template<class T>inline T min(T a,T b,T c,T d) { return min(min(a,b),min(c,d)); } template<class T>inline T max(T a,T b,T c,T d) { return max(max(a,b),max(c,d)); } inline LL Scan() { LL Res=0,ch,Flag=0; if((ch=getchar())=='-')Flag=1; else if(ch>='0' && ch<='9')Res=ch-'0'; while((ch=getchar())>='0'&&ch<='9')Res=Res*10+ch-'0'; return Flag ? -Res : Res; } LL dp[maxn][14];//dp[i][j]为花费 i为血 j为防 LL a[maxx],b[maxx],k[maxn],p[maxn]; int main() { //freopen( "in.txt" , "r" , stdin ); int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { a[i]=Scan();b[i]=Scan(); } for(int i=1;i<=m;i++) { k[i]=Scan();p[i]=Scan(); } for(int i=0;i<maxn;i++) for(int j=0;j<=10;j++) dp[i][j]=LINF; for(int i=0;i<=10;i++)//防御 { dp[0][i]=0; for(int j=1;j<=m;j++) { LL t=p[j]-i;//破防的伤害 if(t<=0) continue; for(int p=t;p<=2003;p++) { dp[p][i]=min(dp[p-t][i]+k[j],dp[p][i]); } } for(int j=2002;j>=0;j--)//单调性 { dp[j][i]=min(dp[j][i],dp[j+1][i]); } } LL ans=0; for(int i=1;i<=n;i++) ans+=dp[a[i]][b[i]]; if(ans>=LINF) puts("-1"); else cout<<ans<<endl; } } 完美AC