Maximizing Sales Profit with Magical Identification

You are given a collection of items in a market. There are two types of items:

• Normal items that have a value \(P\).
• Magical items that have two values: a pre-identification value \(P_1\) and a post-identification value \(P_2\) (with \(P_2 > P_1\)).

To identify a magical item, you must use an identification scroll. When you identify a magical item, the scroll is consumed and you pay \(P_1\) (the pre-identification price) as the cost. After identification, the magical item will sell for \(P_2\). If you do not have enough money to pay for an identification scroll (i.e. if your current money is less than \(P_1\)), you cannot identify that magical item and must sell it as-is for \(P_1\).

You wish to sell all items. Initially, you have no money. However, you can sell normal items at any time to gain money. For a magical item, if you decide not to identify it, you simply get \(P_1\) upon selling it. If you choose to identify it (provided you can pay \(P_1\)) before selling it, you will eventually get \(P_2\), effectively earning an extra profit of \(P_2 - P_1\). The order of sales can be arbitrarily rearranged.

Your task is to determine the maximum amount of money you can end up with after selling all items optimally.

Note: You can assume that if an identification is performed, you pay \(P_1\) (which must be available in your current funds) and then obtain \(P_2\) from the sale. The strategy is to first use sales (of normal items and/or magical items sold without identification) to accumulate some funds, and then identify as many magical items as possible in an order that satisfies the affordability condition.

The final money equals the sum from selling normal items plus the sum from magical items. For each magical item, you have a choice:

• Selling it without identification yields \(P_1\).
• Identifying it yields \(P_2\) but requires you to pay \(P_1\) (which you must have available) before identification. Thus, identifying an item gives you an additional profit of \(P_2 - P_1\).

Your goal is to maximize the total money obtained after all sales.

inputFormat

The input begins with a single integer \(n\) (the number of items).

Then \(n\) lines follow. Each line describes one item. The line starts with an integer \(t\):

• If \(t = 0\), the item is a normal item and the line contains one more integer \(P\) (the value).
• If \(t = 1\), the item is magical and the line contains two more integers \(P_1\) and \(P_2\) (the pre-identification and post-identification values, respectively, with \(P_2 > P_1\)).

You may assume that items can be sold in any order.

outputFormat

Output a single integer, the maximum amount of money obtainable after selling all items optimally.

sample

3
0 5
1 6 100
1 4 10

115