题目描述

商店里有 $n$ 种名称互不相同的商品和 $k$ 个按顺序处理的订单。每种商品给定名称、单件收益和库存数量。每个订单给出商品名称与需求数量，保证订单中的商品名称一定在前面的商品表中出现过。

依次处理每个订单：若库存足够则扣减库存并累加收益（收益 $=$ 单件收益 $\times$ 数量）；若某订单库存不足，则无法满足。

请输出处理完所有订单后的总收益；若存在无法满足的订单，则输出 -X，其中 $X$ 为第一个无法满足的订单编号。

输入格式

第一行两个整数 $n$ 和 $k$；

接下来 $n$ 行，每行一个字符串和两个整数：商品名称、单件收益、库存；

接下来 $k$ 行，每行一个字符串和一个整数：订单的商品名称、需求数量。

输出格式

一行：总收益，或 -X（$X$ 为第一个无法满足的订单编号）。

输入示例 1

2 2
apple 5 10
pear 3 8
apple 3
pear 2

输出示例 1

21

约束条件

• $1 \le n,k \le 10^5$
• 商品名称只含英文字母，长度不超过 $20$，且两两不同
• $0 \le$ 单件收益、库存、订单需求量 $\le 10^9$
• 最终总收益保证在有符号 64 位整数范围内