409788: GYM103743 E Playing Cards

Alice and Bob are playing cards. Each of them has been given $$$n$$$ cards with a number on each card. They will play the cards for $$$n$$$ rounds, and in each round, each player will play a card that hasn't been played before. After both Alice and Bob play a card in a round, they will compare the number written on the cards, and the person who plays a card with a larger number will win this round. In the case that the numbers written on two cards are exactly the same, this round will be a draw.

Alice has a very strong competitive heart. She doesn't want to lose in any round. If in any round she discovered that the number on the card played by her is smaller than the one played by Bob, she will cheat several times. Cheating once, she can increase the number written on her card by $$$k$$$, and she will keep cheating in a round until the number on her card is not smaller than the number on Bob's card.

However, cheating is very risky, therefore she wants to minimize the times of cheating. To achieve that, she managed to know the sequence of cards that will be played by Bob, and she can determine the order to play the cards in her hands. Please help her calculate the minimum cheating times.

Formally, we can denote the cards in Alice's hands by $$$a_1,a_2,\ldots,a_n$$$, and denote the sequence of cards that will be played by Bob by $$$b_1,b_2,\ldots,b_n$$$. You should find a permutation of $$$n$$$ denoted by $$$c_1,c_2,\ldots,c_n$$$, such that

$$$$$$ \sum\limits_{i=1}^n\left\lceil \frac{\max(b_i-a_{c_i},0)}k\right\rceil $$$$$$

is minimized. You should output the minimized value and a possible sequence $$$c_1,c_2,\ldots,c_n$$$.

The first line contains two integers $$$n$$$ ($$$1\leq n\leq 10^5$$$) and $$$k$$$ ($$$1\leq k \leq 10^9$$$), indicating the number of cards on each player's hands and the number that can be increased per cheating action.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1\leq a_i\leq 10^9$$$), denoting the cards on Alice's hands.

The third line contains $$$n$$$ integers $$$b_1,b_2,...,b_n$$$ ($$$1\leq b_i\leq 10^9$$$), denoting the sequence of cards played by Bob. Note that Bob will play the cards in the order of the sequence.

You should output two lines.

In the first line, output a single integer indicating the minimum times to cheat.

In the second line, output $$$n$$$ integers $$$c_1,c_2,...,c_n$$$, indicating the order of cards played by Alice to minimize the cheating times. That is, Alice will play a card with the number $$$a_{c_i}$$$ in round $$$i$$$. If there are multiple answers, print any.

4 2
2 7 6 4
3 9 1 8

2
4 2 1 3