Shopping Cart Billing

For each item, choose the lowest price among its original price and all valid discounts; percentage discounts are rounded down per item before the cart total is computed.

This site's standard I/O format and supplementary bounds follow this problem's statement.

输入格式

The first line contains the number of items n and the number of discount tags d (≤1000). The next n lines are price tagCount tag..., with tagCount=0 when there are no tags; then d lines tag type amount. type=0 is a discounted price, 1 is a percentage discount, and 2 is a fixed amount off.

输出格式

Output the sum of the lowest prices of all items. Tag names are unique; discount amounts are non-negative, percentages are ≤100, and a fixed amount off does not exceed the item's original price.

样例 1

输入：

2 2
10 2 sale pct
7 1 sale
sale 2 3
pct 1 50

输出：

9

样例 2

输入：

1 1
11 0
flat 0 4

输出：

11

样例 3

输入：

4 1
5 2 b c
50 1 b
21 2 b c
19 1 a
a 2 2

输出：

93