U452004 florr.io

[florr](https://florr.io)，启动！

$florr.io$是一款由巴西程序员$M28$制作的网页游戏。在游戏中，玩家扮演花朵打怪升级。不同等级的怪物有不一样的概率掉落特定的花瓣。玩家可以装备花瓣从而提高自身的杀伤力。 假设小$Y$是一个萌新玩家，初始血量为$x$。他事先装备有$m$个花瓣，杀伤力分别为$val_i$$(1\le i \le m)$。小$Y$在后续游戏中最多装备$m$个花瓣。他在$Hel$中不幸 __同时__ 遇到了$n$个怪。每次他可以选择其中的一个怪进行击杀，并获得对应的$k$个花瓣，花瓣本身杀伤力分别为$a_j,_l$。 对于怪物$j$$(1\le j \le n)$，有其血量$b_i$和其每回合伤害$d_i$。小$Y$每次先发起攻击。 小$Y$想知道，他在不死的情况下能获得的最大花瓣总伤害是多少？

第一行，输入四个整数$n$，$m$，$x$，$k$。 第二行，输入$m$个整数$val_i$。 第三行到第$(n+2)$行，输入两个数$b_i，d_i$。 第$(n+3)$行到第$(2n+2)$行，每行输入$k$个整数，表示给出的花瓣$a_j,_l$。

输出一行，表示答案。

小$Y$如果被怪杀死了，他会被传送回主页并无法继续攻击。跟游戏中不一样，如果他伤害了杀死他的怪，他无法获得对应的掉落物。花瓣没有冷却时间。 数据范围：暂无