Problem Description

A smart manufacturing factory has two fully identical automated production lines that can work in parallel, denoted as A and B. The factory has received $N$ production orders at the same time.

For the $i$-th order ($1 \le i \le N$), you are given three parameters:

• Processing time $p_i$: the time required to process this order on either production line.
• Delivery deadline $d_i$: the order must be completed before (and including) hour $d_i$.
• Profit $r_i$: the profit the factory can obtain if the order is completed on time.

Both production lines start running from hour $0$ and are independent of each other. For any production line:

• At any moment, at most one order can be processed.
• Once an order starts processing, it must be completed continuously without interruption.
• There is no switching time between adjacent orders.

The factory may choose any subset of these $N$ orders to produce. For each chosen order, you need to decide:

• Whether to assign it to production line A or production line B.
• Its processing order on the assigned production line.

All chosen orders must be completed within their respective delivery deadlines. Compute the maximum total profit the factory can obtain.

Input Format

The first line contains a positive integer $N$, representing the number of orders.

The next $N$ lines each contain three positive integers $p_i, d_i, r_i$, representing the processing time, delivery deadline, and profit of the $i$-th order.

Output Format

Output one line containing an integer, representing the maximum total profit that can be obtained.

4
3 4 10
3 5 12
2 3 6
4 7 15

43

5
3 4 10
2 3 7
4 6 20
3 7 12
5 8 18

60

Hint

Sample Explanation 1

The information of the four orders is as follows:

One optimal schedule is:

• Production line A: process order $3$ first, then order $2$.
• Production line B: process order $1$ first, then order $4$.

The completion details are:

• Production line A:

  • Order $3$ is processed during hour $0 \sim 2$, with completion time $2$, satisfying $2 \le d_3 = 3$.
  • Order $2$ is processed during hour $2 \sim 5$, with completion time $5$, satisfying $5 \le d_2 = 5$.

• Production line B:

  • Order $1$ is processed during hour $0 \sim 3$, with completion time $3$, satisfying $3 \le d_1 = 4$.
  • Order $4$ is processed during hour $3 \sim 7$, with completion time $7$, satisfying $7 \le d_4 = 7$.

All four orders can be completed on time, and the total profit is:

Sample Explanation 2

The total processing time of the five orders is:

With the latest delivery deadline being $8$, the two production lines can provide at most $16$ units of processing time in the time interval $[0, 8]$, so it is impossible to schedule all orders and finish them on time.

One optimal plan is to give up order $2$ and choose orders $\{1, 3, 4, 5\}$. The schedule is:

• Production line A: process order $3$ first, then order $4$.
• Production line B: process order $1$ first, then order $5$.

The corresponding completion times are:

• Order $3$: completion time is $4$, satisfying $4 \le d_3 = 6$.
• Order $4$: completion time is $7$, satisfying $7 \le d_4 = 7$.
• Order $1$: completion time is $3$, satisfying $3 \le d_1 = 4$.
• Order $5$: completion time is $8$, satisfying $8 \le d_5 = 8$.

These four orders can all be completed on time, so the total profit is:

It can be proven that there is no feasible plan with profit greater than $60$, so the answer is $60$.

Constraints and Notes on Test Cases

• For $30\%$ of the test cases, $N \le 15$.
• For $60\%$ of the test cases, $N \le 50$, and $d_i \le 300$.
• For all test cases, $1 \le N \le 200$, $1 \le p_i \le 50$, $p_i \le d_i \le 1000$, $1 \le r_i \le 10000$.

Translated by ChatGPT 5