#P1555. KD之死

KD之死

题目描述

在 F 出去旅游的这几十年里面,地球上已经发生了翻天覆地的变化。原来 KD 早知道不和谐的地球即将会爆发有史以来的第一次 SC(S**t Combat)大战,这场战争有可能毁灭地球,所以才强行推荐 F 去火星家园,以躲避这次战争。

战争发生的这些年间,KD 带领的正义清扫军顽强抵抗,与敌人势均力敌,才让摇摇欲坠的地球得到残存。可惜世事难料,KD 终是被奸人所害,让敌人从后方攻进基地,应对不及,身受重伤,奄奄一息。(日薄西山,气息奄奄。人命危浅,朝不虑夕。。。。。) SM(S**t Mother):哇嘎嘎嘎嘎嘎,天的光芒在照耀着我,你死定啦,地球就要毁灭啦。

但是 SM 没有发现,那个光芒是由F的拖拉机突破大气层时因摩擦产生火焰而发出的。在地球引力的加速下,拖拉机在 XX 米高空处将 F 弹出后,碰巧飞速撞在了 SM 的身上……SM 惨叫一声后,就戏剧性的消逝了。虽然 KD 眼疾翅快,找了一个屏障,但毕竟是伤痕累累,受不住这么大的冲击,因此也圆寂了……

轰隆……KD 和其他阵亡战士的躯体被装进了重重的 GC 里面,准备送往墓地。由于战争导致的科技极度退化,大家回到了板车时代。所以不得不将这些 GC 一个个竖着叠堆起来放在板车上,并由 SD 拖走。每个盒子都有一个重量 WW 和它所能承受的最大重量 TT,即最多能有 TT 单位重的盒子堆在它上面,否则会把它压烂,显然这个是不包括自身重量的。拖车虽然很顽强坚固,但是毕竟还是拖车,所以也还是有最大承受重量的。

因为和 S 混战了 N 久的 SD 也没多少力气了,所以他不想多次来回拖灵车,因此他只好每次拖运都装上尽量多的盒子。而且,还有更另 SD 抓狂的事:因为有些战士清扫功绩辉煌,所以必须在第一次拖运就将装他们的 GC 送往墓地。由于智商无限,SD 想了半天都没想出来,无奈之下只好求助于过去世界的你,希望你告诉他第一次最多可以装多少个 GC。

输入格式

第一行 33 个正整数 N,M,MAXVN,M,MAXV,表示一共有 NN 个GC,其中有 MM 个GC必须在第一次运到墓地,拖车的最大承受重量是 MAXVMAXV。

接下来 NN 行每行 22 个正整数 WW 和 TT,表示这个 GC 自身重量是 WW 个单位,最大承受量是 TT 个单位。

接下来 MM 行每行一个正整数 PP,表示第 PP 个输入的 GC 第一次必须运到墓地。

输出格式

一个正整数 ANSANS,表示在满足要求的情况下,第一次最多能运多少 GC 到墓地。如果无法满足要求,请输出 Foolish SD!。

样例输入

2 0 6
4 2
2 3

样例输出

2

提示

对于 10%10\% 的数据,N≤10N\leq 10;

对于 40%40\% 的数据,N≤100N \leq 100,W,T≤10000W,T \leq 10000;

对于 100%100\% 的数据,N≤600000N \leq 600000,W,T≤2×109W,T\leq 2 \times 10^9。

题目来源

HNOI2009 集训 Day8。