EIU Programming Practices and Exams

Store chain X implements a membership program with discount policies based on each customer's total previous spending within 1 year (365 days counting backward from the current transaction date).

Discount rates:

• Total spending from 5 million VND and above: 5% discount
• Total spending from 10 million VND and above: 10% discount
• Total spending from 20 million VND and above: 12% discount
• Total spending from 50 million VND and above: 15% discount
• Total spending from 100 million VND and above: 17% discount
• Total spending from 200 million VND and above: 20% discount
• Total spending from 300 million VND and above: 22% discount
• Total spending from 500 million VND and above: 25% discount

Given a list of N transactions, each represented by a triplet (ID_i, T_i, C_i) where:

• IDi is the customer ID for the transaction
• Ti is the day the purchase was made
• Ci is the actual cost paid for that purchase

Knowing that a year has 365 days. Transactions for each customer will be in increasing order of time.

Calculate the total amount of money all customers saved by participating in this membership program compared to not participating.

Input

• The first line contains a single integer N (1 ≤ N ≤ 10⁵), the total number of transactions.
• The next N lines each contain three values: IDi, Ti, and Ci (1 ≤ IDi ≤ 10⁴, 1 ≤ Ti ≤ 10⁵, 1 ≤ Ci ≤ 10⁹) representing the customer ID, purchase day, and actual cost paid, respectively.

Output

A single number representing the total amount of money saved by all customers (round to nearest integer).

Example