Simulation Factory Profit Maximization

You are given a game called Simulation Factory with the following rules:

• At time \(0\), the factory has an initial productivity \(p=1\) and \(0\) goods.
• At every integer time \(t\) (starting at \(0\)), you must choose one of two actions:
  • Boost: The factory's productivity increases by \(1\) at time \(t+1\).
  • Produce: At time \(t+1\) you obtain additional goods equal to the current productivity \(p\) (i.e. goods increase by \(p\)).
• You have a series of orders. There are \(n\) orders. The \(i\)th order is given by \((t_i, g_i, m_i)\) and if you decide to accept it then at time \(t_i\) you must deliver exactly \(g_i\) goods (which will decrease your stored goods by \(g_i\)) and you earn \(m_i\) money. Each order can be accepted at most once and if accepted, it must be executed exactly at time \(t_i\). Multiple orders can occur at the same time.

Your production schedule is under your control. At each time step you choose either to boost productivity or produce goods. This schedule determines the maximum number of goods you may have at any given time. In fact, if you use an optimal strategy before time \(t\) (by doing all boosts as early as possible and then all production actions), the maximum number of goods obtainable by time \(t\) is:

\[ f(t)=\max_{0\le x\le t} (t-x)\,(1+x)=\frac{(t+1)^2}{4} \quad (\text{taking the integer part when necessary}). \]

You must choose a subset of orders to accept such that if the orders are sorted in increasing time, the cumulative goods required by time \(t\) is at most \(f(t)\). Your goal is to maximize the total revenue (sum of \(m_i\)) from the accepted orders.

Input Format: The first line contains an integer \(n\) indicating the number of orders. Each of the following \(n\) lines contains three space‐separated integers \(t_i\), \(g_i\), and \(m_i\) representing an order.

Output Format: Output a single integer — the maximum total revenue you can obtain.

inputFormat

The input begins with an integer \(n\) \( (1 \le n \le \text{small})\) indicating the number of orders. Each of the next \(n\) lines contains three integers \(t_i\) \( (t_i \ge 0)\), \(g_i\) \( (g_i \ge 1)\), and \(m_i\) \( (m_i \ge 0)\) separated by spaces.

outputFormat

Output a single integer which is the maximum total revenue achievable under a valid production schedule and order acceptance plan.

sample

2
5 1 8
7 15 3

11