问题描述

在上次偷袭了B军大本营之后，B军非常愤怒，正式向A军宣战。

A军又获取了一些情报。

B军有n个士兵，每个士兵有a[i]的生命值，以及b[i]的防御力。

A军一共有m个士兵，第i个士兵，需要消耗k[i]的体力，造成p[i]点伤害。

当然，如果A军派出第i个士兵打在B军第j个士兵的话，会使得B军第j个士兵的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。

如果某个B军士兵的生命值降为0或以下，那么这个B军士兵就会被消灭。

假设每个A军士兵都开了挂，可以无限次上阵杀敌，而且从不会受伤。

请问A军最少消耗多少体力，就可以消灭所有的B军士兵。

输入格式

数据的第一行有两个整数n，m,表示B军有n个士兵，A军有m个士兵。

接下来n行，每行两个整数，a[i],b[i]，分别表示B军每个士兵的生命值和防御力。

再接下来m行，每行两个整数k[i]和p[i]，分别表示A军每个士兵的体力消耗和技能的伤害值。

数据范围:

1<=n<=100000

1<=m<=1000

1<=a[i]<=1000

0<=b[i]<=10

0<=k[i]<=100000

0<=p[i]<=1000

输出格式

对于给出的数据，输出最小的体力消耗值，如果不能消灭所有的B军士兵，输出-1。

样例输入

1 2

3 5

10 7

8 6

样例输出

18

哈哈哈，这是动态规划的经典背包题啊！！！！！！！！！！！！

谁是容量谁是价值什么的，自己想，很简单，虽然我敲了半小时。

#include 
    
     #define INF 1e9using namespace std;int k[1005],p[1005];int a[100005], b[100005];int dp[15][1005];int main(){	int n,m;	cin>>n>>m;	for(int i=0;i
     
      =t) dp[i][t]=min(dp[i][t], k[j]);				else dp[i][t]=min(dp[i][t],dp[i][t - (p[j] - i)] + k[j]);			}		}	}	long long re=0;	bool flag=1;	for(int i=0;i