线段覆盖问题的扩展，由最优解变成Kth解，主体上没有太大区别，就是将常规的整数运算扩展到数组的合并操作，思路上没有任何难点，编码上借鉴了归并排序的思路

代码：给予真正需要的人
type

best=record f:array[1..100] of longint; count:longint; end;

link=^node;

node=record t,id:longint; next:link; end;

var

month:array[0..12] of longint=(0,31,28,31,30,31,30,31,31,30,31,30,31);

g:array[1..366] of link;

dp:array[1..366] of best;

w:array[1..100] of longint;

k:longint;

procedure upload(s,t,id:longint);

var

p:link;

begin

{writeln('upload:',s,#32,t);}

new(p);

p^.t:=t;

p^.id:=id;

p^.next:=g[s];

g[s]:=p;

end;

function th(m,d:longint):longint; begin th:=month[m-1]+d; end;

{m1/d1 m2/d2 id}

procedure init;

var

i,t,y,r,m1,d1,m2,d2,id,code:longint;

s:string;

begin

readln(k,t);

{set of month}

readln(y); if ((y mod 100=0)and(y mod 400=0))or((y mod 100<>0)and(y mod 4=0)) then inc(month[2]);

for i:=1 to 12 do inc(month[i],month[i-1]);

readln(r);

for i:=1 to r do begin

readln(s);

val(copy(s,1,pos('/',s)-1),m1,code); delete(s,1,pos('/',s));

val(copy(s,1,pos(#32,s)-1),d1,code); delete(s,1,pos(#32,s)+3);

val(copy(s,1,pos('/',s)-1),m2,code); delete(s,1,pos('/',s));

val(copy(s,1,pos(#32,s)-1),d2,code); delete(s,1,pos(#32,s));

val(s,id,code);

upload(th(m1,d1),th(m2,d2),id);

{writeln('input:',m1,#32,d1,#32,m2,#32,d2,#32,id,#32,#32,th(m1,d1),#32,th(m2,d2));}

end;

for i:=1 to t do readln(w[i]);

end;

procedure merge(a,b:best;w:longint;var c:best);

var

i,j:longint;

begin

i:=1; j:=1;

with c do begin

count:=0;

while (i<=a.count)and(j<=b.count)and(count<k) do
if a.f[i]>b.f[j]+w then begin

if count=0 then begin inc(count); f[count]:=a.f[i]; end

else if f[count]<>a.f[i] then begin inc(count); f[count]:=a.f[i]; end;

inc(i);

end else begin

if count=0 then begin inc(count); f[count]:=b.f[j]+w; end

else begin inc(count); f[count]:=b.f[j]+w; end;

inc(j);

end;

while (count<k)and(i<=a.count) do begin
if count=0 then begin inc(count); f[count]:=a.f[i]; end
else if f[count]<>a.f[i] then begin inc(count); f[count]:=a.f[i]; end;

inc(i);

end;

while (count<k)and(j<=b.count) do begin
if count=0 then begin inc(count); f[count]:=b.f[j]+w; end
else begin inc(count); f[count]:=b.f[j]+w; end;
inc(j);
end;
end;
{writeln('merge(w=',w,')');}
{write('a(',a.count,'):'); for i:=1 to a.count do write(a.f[i],#32); writeln;}
{write('b(',b.count,'):'); for i:=1 to b.count do write(b.f[i],#32); writeln;}
{write('c(',c.count,'):'); for i:=1 to c.count do write(c.f[i],#32); writeln;}
end;
function ans:longint;
var
i:longint;
p:link;
begin
dp[366].count:=1;
dp[366].f[1]:=0;
for i:=365 downto 1 do begin
dp[i]:=dp[i+1];
p:=g[i];
while p<>nil do begin

merge(dp[i],dp[p^.t],(p^.t-i)*w[p^.id],dp[i]);

p:=p^.next;

end;

end;

if dp[1].count =k then ans:=dp[1].f[k]

else ans:=-1;

end;

procedure main;

begin

assign(input,'honey.in');

assign(output,'honey.out');

reset(input);

rewrite(output);

init;

write(ans);

close(input);

close(output);

end;

begin

main;

end.