C. Olympiad Schedule
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Persik — a shark in the world of programming — decided to create a schedule for all tracks of the Innopolis Open olympiad.

There are $$$D$$$ days in the academic year, numbered from $$$1$$$ to $$$D$$$. In total, $$$n$$$ olympiads are held.

The olympiads are numbered from $$$1$$$ to $$$n$$$ in non-decreasing order of their initially scheduled dates. Each olympiad takes place on exactly one day. For each olympiad, its initially scheduled date and its benefit for the younger generation are known.

You may change the date of any olympiad, but only to a later day within the same academic year (that is, the new date cannot be earlier than the original one and cannot exceed $$$D$$$).

After all changes, the olympiads must remain in non-decreasing order of their scheduled dates.

The total benefit of the olympiad season is defined as follows. For each day, consider all olympiads scheduled on that day. If at least one olympiad is scheduled on a given day, the benefit of that day is the maximum benefit among those olympiads. If no olympiads are scheduled on that day, the benefit of that day is $$$0$$$.

The benefit of the season is the sum of the benefits over all $$$D$$$ days.

For the benefit of the students, determine the maximum possible total benefit of the season.

Input

The first line contains three integers $$$n$$$, $$$D$$$, and $$$t$$$ — the number of olympiads and the number of days in the academic year, as well as the type of answer ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le D \le 2 \cdot 10^9$$$; $$$1 \le t \le 2$$$).

In the $$$i$$$-th of the following $$$n$$$ lines, two integers $$$d_i$$$ and $$$b_i$$$ are given — the scheduled date (day number) of the $$$i$$$-th olympiad and its benefit ($$$1 \le d_i \le D$$$; $$$1 \le b_i \le 2 \cdot 10^9$$$).

It is guaranteed that $$$d_i \le d_j$$$ for all $$$i$$$ and $$$j$$$ such that $$$i \lt j$$$.

Output

If $$$t = 1$$$, output a single integer — the maximum possible benefit of the olympiad season.

If $$$t = 2$$$, then in the first line output a single integer — the maximum possible benefit of the olympiad season; and in the second line output the schedule of the olympiads — $$$n$$$ integers, where the $$$i$$$-th is the final date of the $$$i$$$-th olympiad. The specified final dates must achieve the maximum possible benefit of the olympiad season.

Scoring

The tests for this problem consist of thirteen groups. Points for each group are awarded only if all tests of the group and all tests necessary for it are passed.

GroupPointsAdditional constraints Necessary groups
110$$$n, D \le 20$$$; $$$b_i \le 20$$$ for all $$$i$$$; $$$t = 1$$$–
27$$$n, D \le 20$$$; $$$b_i \le 20$$$ for all $$$i$$$1
311$$$n, D \le 100$$$; $$$b_i \le 100$$$ for all $$$i$$$1, 2
49$$$n, D \le 800$$$; $$$b_i \le 800$$$ for all $$$i$$$1, 2, 3
55$$$n, D \le 2500$$$; $$$b_i \le 2500$$$ for all $$$i$$$; $$$t = 1$$$1
64$$$n, D \le 2500$$$; $$$b_i \le 2500$$$ for all $$$i$$$1–5
75$$$b_i = b_j$$$ for all $$$i$$$, $$$j$$$–
85$$$d_i \neq d_j$$$ for all $$$i$$$ and $$$j$$$, such that $$$i \neq j$$$–
95$$$d_i = 1$$$ for all $$$i$$$; $$$t = 1$$$–
105$$$d_i = d_j$$$ for all $$$i$$$, $$$j$$$9
118$$$D \le 2 \cdot 10^6$$$1–6
1210$$$t = 1$$$1, 5, 9
1316–1–12
Examples
Input
3 10 1
1 3
1 5
1 2
Output
10
Input
3 10 2
1 3
1 5
1 2
Output
10
1 2 3
Input
5 6 2
1 7
2 6
5 8
5 9
6 4
Output
30
1 3 5 6 6
Note

Note that the answer for the second test will not be suitable as an answer for the first, as for $$$t = 1$$$ only one number needs to be output.

In the second example, the benefit of the first day is $$$3$$$, the benefit of the second is $$$5$$$, the third is $$$2$$$, and the benefits of days from the $$$4$$$th to the $$$10$$$th are $$$0$$$. Thus, the benefit of the olympiad season is $$$3+5+2+0+\ldots+0=10$$$. Note that the schedule of olympiads $$$[2, 1, 3]$$$ is not possible, as the olympiads must remain in non-decreasing order of their scheduled dates.

In the third example, a schedule of olympiads $$$[1, 2, 5, 6, 6]$$$ is also suitable, but $$$[1, 2, 3, 5, 6]$$$ is not suitable, as the third olympiad cannot take place before the $$$5$$$th day