【题目描述】：
    有n个带标号的珠子，第i个珠子的价值为a[i]。现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。现在给所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。请输出第k小的项链的价值，以及所用的珠子集合。
【题目解法】：
    我们可以考虑用bfs来扩展出第一问的答案，如何快速扩展出来呢？
    显然我们要使得扩展出来的状态尽量优并且无关状态尽量少
    因此我们考虑贪心，我们现将a数组排序，然后用(x,y)表示最大值为a[x]总和为y的状态
    然后我们扩展：(x+1,y-a[x]+a[x+1]) (x+1,y+a[x+1])，也就是a[x]是否选
    然后每次拿出最小y的状态来扩展，扩展k次即可得出答案。
    我们证明一下正确性：
    显然如果没有扩展到(x,y)，那么也就是说最大x的状态为(x1,y1)其中x1<x
    那么显然如果某个状态(x,y)比(x1,y1)都要优，那么显然y1<y
    然后我们构造一个方案：(x3,y2=y1-a[x1]+a[x])，由于x<x1那么a[x]<a[x1]，因此y2<y1，并且x3<x1，因此(x1,y1)不是最优的
    因此我们这样扩展保证了所有没有扩展出来的状态至少比队列中的某一个状态要差，因此扩展的状态一定是最优的
    然后我们考虑复杂度，由于每次扩展一个节点变成两个节点，因此每次总的多了一个节点，队列中最多有k个节点，因此复杂度为O(K log K)
    然后我们考虑第二问。我们假设第一问答案为ans
    那么显然我们知道方案<=ans最多有k个
    因此我们顺着字典序暴力dfs，每次我们找到最高前的且加上去不超过ans的数的位置，然后向下dfs
    这样子由于每次的总和保证小于ans，因此最多dfs到k个状态，每次查找使用线段树
    总的复杂度为O(K log n)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=1000005;
const int INF=32083208;
struct node
{
    int pos; long long val;
    bool operator < (const node &a) const
    {
        return val>a.val;
    }
};
int n,m,Ans[N]; long long ans,a[N],b[N],c[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint(); m=getint(); ans=0;
    for (int i=1; i<=n; i++) c[i]=a[i]=getint();
    sort(a+1,a+n+1);
}
namespace Task1
{
    __gnu_pbds::priority_queue<node> Q;
    void solve()
    {
        b[1]=0; int expand=1; Q.push((node){1,a[1]});
        while ((!Q.empty())&&(expand<m))
        {
            node now=Q.top(); Q.pop(); ans=now.val; expand++;
            b[expand]=ans; if (now.pos==n) continue;
            Q.push((node){now.pos+1,now.val+a[now.pos+1]});
            Q.push((node){now.pos+1,now.val-a[now.pos]+a[now.pos+1]});            
        }
        printf("%lld\n",ans);
    }
}
namespace Task2
{
    struct node {int mint,maxt;} tree[N*4];
    int rest,cnt;
    void build(int p,int l,int r)
    {
        int mid=(l+r)/2;
        if (l==r) {tree[p].mint=tree[p].maxt=c[l]; return;}
        build(p*2,l,mid); build(p*2+1,mid+1,r);
        tree[p].mint=min(tree[p*2].mint,tree[p*2+1].mint);
        tree[p].maxt=max(tree[p*2].maxt,tree[p*2+1].maxt);
    }
    int ask(int p,int l,int r,long long x)
    {
        if (x>=tree[p].maxt) return l;
        if (x<tree[p].mint) return INF;
        int mid=(l+r)/2; int nowans=INF;
        nowans=ask(p*2,l,mid,x); if (nowans!=INF) return nowans;
        nowans=ask(p*2+1,mid+1,r,x); return nowans;
    }
    int ask(int p,int l,int r,int ll,int rr,long long x)
    {
        if (ll>rr) return INF; int mid=(l+r)/2;
        if ((l==ll)&&(r==rr)) return ask(p,l,r,x);
        if (rr<=mid) return ask(p*2,l,mid,ll,rr,x);
        else if (ll>mid) return ask(p*2+1,mid+1,r,ll,rr,x);
        else return min(ask(p*2,l,mid,ll,mid,x),ask(p*2+1,mid+1,r,mid+1,rr,x));
    }
    void dfs(int p,long long val)
    {
        if (val>ans) return;
        if (rest==0) return;
        if (val==ans)
        {
            rest--; if (rest!=0) return;
            for (int i=1; i<=cnt; i++) printf("%d ",Ans[i]);
            printf("\n"); return;
        }
        for (;p!=INF;)
        {
            p=ask(1,1,n,p+1,n,ans-val); if (p==INF) return;
            Ans[++cnt]=p; dfs(p,val+c[p]); Ans[cnt--]=0;
        }
    }
    void solve()
    {
        if (ans==0) return;
        for (int i=m; i>=1; i--) if (b[i]==ans) rest++;
        build(1,1,n);
        dfs(0,0);
    }
}
int main()
{
    init();
    Task1::solve();
    Task2::solve();
    return 0;
}