问题描述

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

Format

Input

第1行2个整数n和k，k≤n≤10⁵。 下面的n行，每行表示一种商品的名称，收益和库存3种信息。 再下面的若干行，每行表示一个订单的需求商品和需求数量两种信息。 每种商品的个数保证在int范围内，保证每个订单中都不会出现没有的商品，商品名的长度≤20。

Output

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

Samples

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

443

Limitation

1s, 1024KiB for each test case.