题意
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有$n$个怪兽，每个怪兽有$a[i]$的生命值，以及$b[i]$的防御力。
度度熊一共拥有$m$种攻击方式，第$i$种攻击方式，需要消耗$k[i]$的晶石，造成$p[i]$点伤害。
当然，如果度度熊使用第$i$个技能打在第$j$个怪兽上面的话，会使得第$j$个怪兽的生命值减少$p[i]-b[j]$，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为$0$或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。
数据范围:
$1 \le n \le 100000$
$1 \le m \le 1000$
$1 \le a[i] \le 1000$
$0 \le b[i] \le 10$
$0 \le k[i] \le 100000$
$0 \le p[i] \le 1000$
思路
看到这题，让我感觉和NOIP2014 飞扬的小鸟一题很像。于是回想起了那正是在apec蓝之际，我和wsc同学从八十中考场走出来，被此地路上几乎没车，天上十分清澈的景象深深震撼到了。在分析了一番为什么几乎没车，天为什么这么蓝之后。我们坐上了公交车，准备回学校。在公交车上，我们开始讨论飞扬的小鸟，此时出现了一位形似男而音似女的同学，对我俩说这题的$DP$他没有想好转移方程怎么写。我们两个显然当时被他惊呆了，我也忘了后来我们说了什么，只记得下车后我疑惑地问wsc那个同学是男是女。现在我才知道，原来人并非非男即女，性别也是有很多种的，只是当时太年轻不懂这么多23333。我们回到了玉泉路，到了小豆面馆，只记得两人各吃了两份套餐，现在看我们真是食量惊人。貌似。。。跑题了？
我们回到这个题目上,这题显然是个背包，甚至就是飞扬的小鸟的简化版。我们用$dp[i][j]$表示消灭血量为$i$，防御力为$j$的怪兽需要的最少晶石数。那么显然可以得到转移方程$dp[i][j]=min(dp[i-p_t+j]+k_t)$,其中$p_t$代表第$t$个攻击可以减少的生命值，$k_t$代表第$t$个攻击消耗的晶石数。时间复杂度为$O(m \times A \times B)$，其中$m \le 1000$为攻击种数，$A \le 1000$为生命值，$B \le 10$为防御力。
代码
#define OJ
#define lld I64d
//#define local
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
using namespace std;
const int Nmax=1e6+7;
#ifdef OJ
typedef __int64 ll;
#endif
#ifdef local
typedef long long ll;
#endif
const ll INF=1e9+7LL;
int n,m;
struct J
{
ll t,p;
}jnn[Nmax];
ll a[Nmax],b[Nmax];
ll mb,mp,ma;
ll dp[Nmax][15];
void init()
{
for(int j=0;j<=1000;j++)
for(int i=0;i<=10;i++)
dp[j][i]=j==0?0LL:INF;
//dp[j][i]=0;
ma=mb=mp=0;
}
int main()
{
#ifdef local
freopen("c.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&a[i],&b[i]);
mb=max(mb,b[i]);
ma=max(ma,a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&jnn[i].t,&jnn[i].p);
mp=max(mp,jnn[i].p);
}
if(mp<=mb)
{
printf("-1\n");
continue;
}
for(int j=0;j<=10;j++)
{
for(int i=1;i<=ma;i++)
{
for(int k=1;k<=m;k++)
{
if(jnn[k].p<=j)
continue;
ll next=max(0LL,i-jnn[k].p+j);
dp[i][j]=min(dp[i][j],dp[next][j]+jnn[k].t);
}
}
}
ll ans=0LL;
for(int i=1;i<=n;i++)
ans+=dp[a[i]][b[i]];
printf("%lld\n",ans);
}
return 0;
}
