B. Selling Apartments
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  • sell exactly one apartment that he has not sold before; or
  • not sell anything.

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).

Input

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.

Output

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.

Scoring
GroupPoints Additional Constraints Required Groups
17$$$k = 1$$$–
219$$$k = t$$$–
317All $$$a_i$$$ are equal–
417All $$$b_i$$$ are equal–
540–1, 2, 3
Examples
Input
6 2 4
10 1
15 1
8 2
14 3
14 3
14 3
Output
53
5 1 6 2 
Input
6 3 8
10 1
10 1
10 1
20 2
20 2
20 2
Output
90
4 1 -1 5 2 -1 6 3