Boris the Beaver is selling apartments at a very favorable (for him) price. Help him earn as much as possible in $$$t$$$ days!
There are $$$n$$$ apartments, numbered from $$$1$$$ to $$$n$$$ in the order given in the input data. Apartment $$$i$$$ has a price of $$$a_i$$$ and is located in district $$$b_i$$$.
The sales days are numbered from $$$1$$$ to $$$t$$$. Each day, Boris can:
Each time he sells, Boris claims that he has lived in the apartment for the last few years (this argument helps sell the apartment for a higher price), so in one district for $$$K$$$ consecutive days, he can sell at most one apartment (otherwise, the residents of that district would notice that Boris has several apartments).
The first line contains three integers $$$n$$$, $$$K$$$, $$$t$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le K \le 10^5$$$, $$$1 \le t \le 10^5$$$).
The next $$$n$$$ lines contain pairs of integers $$$a_i$$$, $$$b_i$$$ ($$$0 \le a_i \le 10^9$$$, $$$1 \le b_i \le n$$$) — the price of the apartment and the district number in which it is located.
In the first line, output a single integer — the maximum possible revenue for Boris over $$$t$$$ days.
In the second line, output $$$t$$$ integers. The $$$d$$$-th number should be the number of the apartment sold on day $$$d$$$, or $$$-1$$$ if Boris does not sell an apartment on that day.
If there are multiple optimal answers, output any.
| Group | Points | Additional Constraints | Required Groups |
| 1 | 7 | $$$k = 1$$$ | – |
| 2 | 19 | $$$k = t$$$ | – |
| 3 | 17 | All $$$a_i$$$ are equal | – |
| 4 | 17 | All $$$b_i$$$ are equal | – |
| 5 | 40 | – | 1, 2, 3 |
6 2 410 115 18 214 314 314 3
53 5 1 6 2
6 3 810 110 110 120 220 220 2
90 4 1 -1 5 2 -1 6 3
| Name |
|---|


