题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXV Olimpiada Informatyczna — II etap Tomik poezji

著名诗人 Bajtazar 计划出版一本诗集，收录他的 $n$ 首最新诗作。每页可印刷 $s$ 行文字，诗作按顺序逐一印刷，中间无间隔。每首诗包含标题（占一行）及其后续正文，第 $i$ 首诗的正文占 $a_i$ 行。

为美观起见，标题不得印刷在页面最后一行。若前一首诗结束于页面倒数第二行，则该页最后一行需留空。Bajtazar 的诗作顺序未定，不同排列可能导致不同数量的空行。他想找出一种诗作排列，尽量减少诗集内的空行数。

输入格式

第一行包含两个整数 $n, s$ $(n \geq 1, 2 \leq s \leq 1000000)$，分别表示诗作数量和每页行数。诗作编号为 $1$ 至 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 1000000)$，表示各诗作正文的行数。

输出格式

输出两行：

第一行包含一个整数 $k$，表示诗集中最少的空行数。

第二行包含 $n$ 个互不相同的整数（范围 $[1, n]$），表示一种需 $k$ 空行的诗作排列，数字间以单空格分隔。若有多解，输出任意一种。

3 5
2 5 1

0
2 3 1

提示

样例 1 解释

按顺序印刷（$1,2,3$），诗作间有一空行：

$$\begin{array}{|c|} \hline \texttt{1111} \\ \texttt{WWWW} \\ \texttt{WWWW} \\ \texttt{2222} \\ \texttt{WWWW} \\ \hline \end{array} \begin{array}{|c|} \hline \texttt{WWWW} \\ \texttt{WWWW} \\ \texttt{WWWW} \\ \texttt{WWWW} \\ \texttt{....} \\ \hline \end{array} \begin{array}{|c|} \hline \texttt{3333} \\ \texttt{WWWW} \\ \\ \\ \\ \hline \end{array} $$

最优排列（$2,3,1$）无空行：

$$\begin{array}{|c|} \hline \texttt{2222} \\ \texttt{WWWW} \\ \texttt{WWWW} \\ \texttt{WWWW} \\ \texttt{WWWW} \\ \hline \end{array} \begin{array}{|c|} \hline \texttt{WWWW} \\ \texttt{3333} \\ \texttt{WWWW} \\ \texttt{1111} \\ \texttt{WWWW} \\ \hline \end{array} \begin{array}{|c|} \hline \texttt{WWWW} \\ \\ \\ \\ \\ \hline \end{array} $$

附加样例

1. $n=5, s=2$。
2. $n=1000, s=100, a_i=98$，每种排列需 $999$ 空行。
3. $n=1000, s=1003, a_i=i$，诗作 $i$ 和 $n+1-i$ 恰填满一页，无空行。

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 10$	$10$
$2$	$n \leq 500000$，$a_i$ 两两不同，$a_i \leq s$	$20$
$3$	$n \leq 1000$	$25$
$4$	$n \leq 500000$	$45$