A traveling fairground wants to close out the weekend by ranking its visitors on a spending leaderboard. Every game booth charges a fixed number of tickets per play, and the front desk has a log of every time a visitor redeemed one or more plays at a booth. For each visitor, compute the total number of tickets they spent across every redemption in the log, then rank the visitors from biggest spender to smallest.

Input format

Line 1 contains two integers B and K — the number of booths and the number of redemption records. Each of the next B lines contains two integers booth_id and cost — the number of tickets it costs to play that booth once. All booth_id values are distinct. Each of the next K lines contains three integers visitor_id, booth_id, and plays — meaning that visitor redeemed plays turns at that booth. The same visitor may appear on multiple lines (at the same booth or different booths), and every booth_id referenced in a redemption line is guaranteed to appear exactly once among the booth lines.

Output format

Print one line per distinct visitor who appears in at least one redemption record, formatted as visitor_id spent, where spent is the sum over all of that visitor's redemption lines of plays * cost (using the cost of the referenced booth). Order the lines by spent descending; break ties by visitor_id ascending. Booths with no redemptions produce no output line.

Constraints

• 1 <= B <= 500
• 1 <= K <= 2000
• 1 <= booth_id, visitor_id <= 10^6
• 1 <= cost <= 10000
• 1 <= plays <= 10000
• Total spending for a visitor can exceed the 32-bit signed integer range; use 64-bit integer arithmetic.

2 4
7 10
9 15
501 7 4
501 9 2
502 9 4
503 7 6

501 70
502 60
503 60

1 1
3 5
200 3 7

200 35