「XXIII Olimpiada Informatyczna」珠子

题目描述

Bajtyna 有 $n$ 颗编号从 $1$ 到 $n$ 的珠子，每颗都不相同，且各有其价值（以字节币计价）。她想用这些珠子制作一条项链，但可选的组合方式有很多。若两条项链使用的珠子集合不同，就算不同。为了方便选择，Bajtyna 决定给所有可能的项链组合排序。

排序的首要标准是项链中珠子的总价值，总价值越大，排名越靠后。若两个组合的总价值相同，则按珠子编号升序排列后的列表进行字典序比较。

例如，假设有四颗珠子，价值依次为（按编号）$3,7,4,3$ 字节币，可组成 $16$ 种项链。以下是按 Bajtyna 规则排序的组合：

字节娜想知道第 $k$ 个组合的项链是怎样的。请你帮她设计！

输入格式

输入第一行包含两个正整数 $n$ 和 $k$，分别表示珠子数量和目标组合的排名。

第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$，表示各珠子的价值。

保证存在至少 $k$ 种不同的项链组合。

输出格式

第一行输出一个整数，表示目标组合中珠子的总价值。

第二行输出目标项链使用的珠子编号，按升序排列，数字间用空格分隔。若 $k=1$，第一行输出 $0$，第二行留空。

样例

输入

4 10
3 7 4 3

输出

10
1 3 4

附加样例

• $n=10$，所有珠子价值为 $1$；
• $n=9$，珠子价值为 $2$ 的连续幂次；
• $n=11$，一个珠子价值 $1$，十个价值 $10^{9}$，答案使用全部 $11$ 颗珠子；
• $n=1000000, k=10$，珠子价值依次为 $1$ 到 $1000000$。

数据范围与提示

所有子任务满足 $n, k \leq 1000000$ 且 $a_{i} \leq 10^{9}$。

若第一行（总价值）正确但第二行错误，可获该测试点一半分数（即使第二行缺失或多输出）。

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