P5967 [POI 2016] Korale

There are $n$ labeled beads. The value of the $i$-th bead is $a_i$. Now you may choose some beads to form a necklace (you may also choose none). The value of a necklace is the sum of the values of all beads in it. Consider all possible necklaces and sort them: first by total value in increasing order; if the total values are the same, sort by the lexicographical order of the set of used bead labels in increasing order. Output the value of the $k$-th smallest necklace and the set of bead labels used.

The first line contains two positive integers $n,k$. The second line contains $n$ positive integers, where the $i$-th number is the value $a_i$ of the $i$-th bead.

Output the value of the $k$-th smallest necklace on the first line. On the second line, output the labels of all beads in this necklace in increasing order.

Constraints: for $100\%$ of the testdata, $1\le n\le 10^6$, $1\le k\le \min(2^n,10^6)$, $1\le a_i\le 10^9$. Translated by ChatGPT 5