Problem Description

Xiao Lan is a project manager at a company and needs to handle a large number of tasks every day. Now the company has a total of $N$ tasks to complete, and each task takes one day.

Days start from day $1$ and are numbered by positive integers as day $1$, day $2$, day $3$, and so on. Xiao Lan can complete at most one task per day, and may also leave a day with no task scheduled.

Each task has a deadline $t$ and a value $w$. If the task is completed on day $t$ or earlier, it can create value $w$ for the company; if it exceeds the deadline, the task becomes invalid and can no longer be completed.

Among these tasks, some are marked as core tasks. The company requires that when Xiao Lan makes a schedule, they must first maximize the number of completed core tasks; among all schedules that satisfy this, they should then maximize the total value of all completed tasks.

Now, please help Xiao Lan compute: the maximum number of core tasks that can be completed, and under the condition that the number of completed core tasks is maximized, the maximum total value that can be obtained.

Input Format

The first line contains a positive integer $N$, indicating the total number of tasks.

The next $N$ lines each contain three integers $t_i, w_i, \text{is\_key}_i$, representing the deadline, value, and whether the $i$-th task is a core task, respectively.

Here, $\text{is\_key}_i = 1$ means it is a core task, and $\text{is\_key}_i = 0$ means it is a normal task.

Output Format

Output one line containing two integers, representing the maximum number of core tasks that can be completed, and under this condition, the maximum total value that can be obtained.

4
3 10 1
1 5 1
2 100 0
1 100 0

2 115

Hint

Sample Explanation

To prioritize completing as many core tasks as possible, Xiao Lan can schedule task $2$ on day $1$ and task $1$ on day $3$. In this way, they can complete $2$ core tasks, with a total value of $15$.

While keeping the completion of $2$ core tasks, they can also schedule task $3$ on day $2$, making the total value $5 + 100 + 10 = 115$. The deadline of task $4$ is day $1$, and it can no longer be completed on time.

Constraints and Notes for Test Cases

For $30\%$ of the test cases, $1 \le N \le 1000$, $1 \le t_i \le 1000$.

For all test cases, $1 \le N \le 2 \times 10^5$, $1 \le t_i \le 10^9$, $1 \le w_i \le 10^9$.

Translated by ChatGPT 5