首先选取的线段一定是相邻两个端点线段，那么我们贪心的考虑这个问题，我们先在这n-1条线段中选出最短的一条，然后将这条线段的值改为左面的线段的值+右面的线段的值-自己的值，用这条线段取代原来这三条线段，继续做，那么这个取m次出来之后的就是答案，对于证明，我们可以大概的去想，选了新的线段代表不选这条原本的线段，然后选另两条相邻的线段，这样选的线段的条数只是+1，相当于又取了一条线段，正确性的证明可以大概感知。

　　至于选最小的用堆来维护就行了，因为需要删除精确到点编号，对堆用的不熟悉，所以用sbt代替。

/**************************************************************    Problem: 1150    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:2708 ms    Memory:11956 kb****************************************************************/ //By BLADEVILtype    pointer=^rec;    rec                     =record        pred, succ          :pointer;        num, fuck           :int64;    end;    shit                    =record        shit1, shit2        :longint;    end;     var    n, m                    :longint;    a                       :array[0..200100] of pointer;    left, right, size       :array[0..400100] of longint;    key, adr                :array[0..400100] of longint;    t, tot                  :longint;    ans                     :int64;     procedure left_rotate(var t:longint);var    k                       :longint;begin    k:=right[t];    right[t]:=left[k];    left[k]:=t;    size[k]:=size[t];    size[t]:=size[left[t]]+size[right[t]]+1;    t:=k;end; procedure right_rotate(var t:longint);var    k                       :longint;begin    k:=left[t];    left[t]:=right[k];    right[k]:=t;    size[k]:=size[t];    size[t]:=size[left[t]]+size[right[t]]+1;    t:=k;end; procedure maintain(var t:longint;flag:boolean);begin    if not flag then    begin        if size[left[left[t]]]>size[right[t]] then            right_rotate(t) else        if size[right[left[t]]]>size[right[t]] then        begin            left_rotate(left[t]);            right_rotate(t);        end else exit;    end else    begin        if size[right[right[t]]]>size[left[t]] then            left_rotate(t) else        if size[left[right[t]]]>size[left[t]] then        begin            right_rotate(right[t]);            left_rotate(t);        end else exit;    end;    maintain(left[t],false);    maintain(right[t],true);    maintain(t,true);    maintain(t,false);end;     procedure insert(var t:longint;v,k:int64);begin    if t=0 then    begin        inc(tot);        t:=tot;        left[t]:=0;        right[t]:=0;        size[t]:=1;        key[t]:=v;        adr[t]:=k;    end else    begin        inc(size[t]);        if v
     
      key[t] then insert(right[t],v,k) else        if v=key[t] then            if k>adr[t] then insert(right[t],v,k) else                insert(left[t],v,k);        maintain(t,v>=key[t]);    end;end; function delete(var t:longint;v,k:int64):shit;var    damn                    :shit;begin    dec(size[t]);    if (v=key[t]) and (k=adr[t]) or (v>key[t]) and (right[t]=0) or (v
      
       key[t] then delete:=delete(right[t],v,k) else            if v=key[t] then                if k>adr[t] then delete:=delete(right[t],v,k) else                if k