题目描述

商店有 $n$ 种商品和按时间顺序给出的 $k$ 个订单。每种商品有名称、单件收益、库存。必须依序满足订单；若全部满足，求总收益；否则找出第一个无法满足的订单。

输入格式

第一行 $n,k$。随后 $n$ 行每行商品名、单件收益、库存；再给 $k$ 行，每行商品名、需求数量。商品名称唯一，订单中的商品一定存在。

输出格式

全部满足时输出总收益，否则输出 -x，其中 $x$ 为第一个失败订单的编号（从1开始）。

样例

1 1
ga 948 2147483647
ga 2147483647

2035814497356

数据范围

$1\le n,k\le10^5$；商品名仅含小写字母且长度1至20；库存、需求数量在0至 $2^{31}-1$；单件收益在0至10000。