St. Robert CHS Annual Winter Coding Contest: Problem 4

Contributing to the Christmas magic are the plethora of Christmas animations that families can watch together—for example, part of a family movie-night.

This year, you and your family are intent on binge-watching as many Christmas specials as possible! You've compiled a list of \(N\) (\(1 \le N \le 10^5\)) such specials, the \(i\)-th of which you intend to watch from time \(a_i\) to \(b_i\) (\(1 \le a_i, b_i \le 10^9\)). Each special has a Tomatometer score \(s_i\) (\(1 \le s_i \le 10^4\)), taken from Rotten Tomatoes and indicating its "quality".

You and your family want to figure out what Christmas specials to watch so that you can maximize the sum of Tomatometer scores of watched films. However, there's some restrictions in place.

1. You cannot watch two shows simultaneously. In particular, if one show is from \(3\) to \(5\), and another is from \(5\) to \(6\), they will intersect meaning you cannot choose to watch both.
2. If you want to watch show \(i\) after show \(j\), you must ensure that \({a_i}^2-{b_j}^2-2{a_i}{b_j} \ge 0\)

Given these requirements, what is the maximum sum of Tomatometer scores?

Image: Rudolph the Red-Nosed Reindeer (1964)

Input Specification

The first line will contain one integer \(N\).
The next \(N\) lines will each contain three-space separated integers \(a_i\), \(b_i\), and \(s_i\).

For \(30\)% of the marks to this problem, \(1 \le N \le 1000\).

Output Specification

Output one integer, what is the maximum sum of Tomatometer scores?

Sample Input

2
1 3 5
10 20 7

Sample Output

12