3659: Rp病毒攻击-训练套题T17T4

4.Rp病毒攻击 rp.pas/in/out

    已知机房的计算机网络是一棵完全二叉树,中毒计算机即为该树的根节点，从该计 算机开始向下发送攻击数据包。除中毒机外每台计算机可以选择安装某一种病毒防火墙，来 保护现有数据（也可以不安装病毒防火墙）。安装某种病毒防火墙需要一定费用，假定某种病毒防火墙费用为 b 元，有 k 台计算机安装此病毒防火墙，则总共需要花费 k*b 元。每台 计算机受到损失=受到攻击数据大小-病毒防火墙阻截能力。每台计算机受到攻击后，又会 向下发送攻击数据包。由于有的计算机有其他病毒，因此它向下发送的攻击数据包可能会成倍放大,即发送的数据包大小=(受到攻击数据包大小-病毒防火墙阻截能力)*放大倍数。

注意 :受到损失最大为原数据价值，向下发送的攻击 数据包与损失多少无关。现在

MZOIers 手中经费有限，你的任务是选择一种病毒防火墙安装方案，使损失数据最少。

【输入文件】

rp.in 中共 n+m 行： 第一行，四个整数，n，m，money，attack。分别为计算机总台数，可以选择的防护

墙种数，总共经费，病毒源最初发出的攻击包大小。

从第二行到第 n 行，每行两个整数 a,b，分别为第 2 台到第 n 台计算机每台计算机的 数据价值与它可能在输出攻击时将攻击包放大的倍数。(根节点无价值且也不再将攻击包放 大)

从第 n+1 行到第 n+m 行，每行两个整数 c,d，分别为每种病毒防火墙的费用和它的阻 截能力。

【输出文件】

rp.out 中只有一个整数，为最小损失值。

【输入样例】

4 1 10 10

101

101

101

10 10

【样例输出】

10

【数据规模】

对于全部的数据，保证有

1=<n<=100; 1=<m<=20;

0=<Money<=100; 1=<Attack<=100;

0=<a<=100; 1=<b<=3;

1=<c<=100; 0=<d<=100