wky巨佬第100000次ak-ioi……

为了给其他人一点追上他的机会，他决定去旅行

旅行需要带很多东西，每件的空间为w[i],所占价值为v[i]

已知wky巨佬有n种物品,最多能带的空间为m，且每种物品的数量为1

但物品带多了对价值是有影响的,当wky巨佬带的物品空间为i时，价值就要减去t[i](t[i]>=t[i-1]且t[0]=0)

wky巨佬想知道他最多的价值是多少

当然，他怎么会有兴趣做这么弱智的题呢?于是这个问题就到了你头上

第一行两个数n，m

接下来n行，每行两个数w[i],v[i]

接下来一行共m个数,表示t[i]

输出一行一个数表示最大收益

  1<=n<=1000,1<=m<=5*10^4 ,1<=v[i],t[i]<=5*10^4