6281 - 最大收益

商店里有 n 种商品和 k 个按顺序给出的订单。每种商品给定名称、收益和库存。每个订单给出需求商品和需求数量。编程判断是否能依序满足所有的订单,如果可以,输出收益;否则,输出“- X ”, X 表示第一个无法满足的订单编号。

输入

第 1 行 2 个 整 数 n 和 k ,k≤n≤10^5

下面的 n 行,每行表示一种商品的名称、收益和库存3种信息。

再下面的若干行,每行表示一个订单的需求商品和需求数量两种信息。

每种商品的个数保证在 int 范围内,保证每个订单中都不会出现没有的商品,商品名的长度≤20。

输出

一行一个整数,表示收益,或者“_ X”, X 表示第一个无法满足的订单编号。 

样例

输入

3 5
apple 1 100
pear 5 90
football 30 10
Pear 24
apple 18
foottball 4
pear 1
football 6

输出

443

来源

课课通

时间限制 1 秒
内存限制 32 MB
讨论 统计
上一题 下一题