[问题的模型]
　　在数轴上有一些线段，线段具有权值。一种方案是指一组没有重叠的线段的集合，一种方案的总收益就是这些被选线段的权值和。在所有的方案中，求第k大的收益。

[问题分析]
　　该题用动态规划解。

　　先考虑k=1的情况，即每次取最大值。这题线段端点的范围较小(从1到366)，适合做阶段。设f(d)表示前d天可以达到的最大收益，Sd表示右端点在第d天的线段集合。

　　(1) 如果f(d)不选取中的任意线段，则f(d) = f(d-1)
　　(2) f(d)只选择中的某条线段(只能选取一条，因为中线段右端点都相同，选取多条就冲突了)。设选择线段x，其左端点为d'，权值为w。显然，当f(d)最大时，前d'天的收益也最大。因此，f(d) = f(d') + w。
　　于是，得到状态转移方程：
　　
　　其中，x.d'表示线段x的左端点，x.w表示x的权值。

　　考虑k≠1的情况。
　　前d天收益第k大的方案中，前j天(j < d)的收益也是前k大的。因此k≠1的情况可以和k=1的情况类似处理。如果要求的最后结果为第k大，只要在每一个阶段都保留前k大的结果。设f(d, n)为前d天可以达到的第n大收益。在计算f(d)的过程中，每次处理x∈ 时，可以建立临时数组g，g[i]表示选择了线段x，前d天可以达到的第i大的收益值。于是，g[i] = f(d', i) + x.w (1 ≤ i ≤ k)，然后再把g和f(d)进行归并取前k大。

[复杂度]
　　f的每个元素都是长整型的，因此需要3671004 = 146800 bytes的空间。线段集合S最多有20000个元素，每个元素要8 bytes，一共要200008 = 160000 bytes。因此本一共大约要300K，是可以承受的。这里，f(d)使用指针数组，而则用链表存储。

　　按天数划分阶段，实际上处理了每条线段，对一条线段的处理是求临时数组g和归并排序这两个过程，这两项的复杂度都是O(k)级的，所以算法总的复杂度O(r k)，可以接受。

[小结]
　　实际上该题就是把求最大值推广到了求第k大值，按照求最大值的动态规划，可以得出该题的解法。

[参考程序]

{$R-,Q-,S-,T-,V-,W-,X-,Y-}
const
　FileIn = 'honey.ina';
　FileOut = 'honey.out';
　Days : array[0..12]of integer
　　　= (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365);
type
　TDay = ^PDay;
　PDay = record
　　　　d1, d2 : integer;
　　　　GType : byte;
　　　　Pay : Longint;
　　　　next : TDay;
　　　end;
　EachDay = array[1..100]of Longint;
var
　Request : array[1..366]of TDay;
　　r : integer;
　k, k2, t : byte;
　　latest : integer;
　　　cost : array[1..100]of longint;
　ti, ans : Longint;
　　　　d : array[0..366]of ^EachDay;

procedure Initialize;
var day1, day2 : integer;
　　　i, code : integer;
　　　　　　F : text;
　　　　　　s : string;
　p : TDay;

　procedure process;
　var m, d, j : byte;
　　s1 : string;
　begin
　　j := pos(' ', s); s1 := copy(s, 1, j - 1); delete(s, 1, j + 3);

　　j := pos('/', s1); val(copy(s1, 1, j - 1), m, code);
　　val(copy(s1, j + 1, length(s1) - j), d, code);
　　day1 := days[m - 1] + d;

　　j := pos(' ', s); s1 := copy(s, 1, j - 1);
　　delete(s, 1, j);

　　j := pos('/', s1); val(copy(s1, 1, j - 1), m, code);
　　val(copy(s1, j + 1, length(s1) - j), d, code);
　　day2 := days[m - 1] + d - 1;

　　new(p);
　　p^.d1 := day1;
　　p^.d2 := day2;
　　val(s, p^.Gtype, code);
　　p^.next := request[day2];
　　request[day2] := p;

　　if day2 > latest then latest := day2;
　end;

begin
　assign(f, filein); reset(f);
　readln(f, k, t);
　readln(f, i);
　if (i mod 400 = 0) or (i mod 4 = 0) and (i mod 100 <> 0) then
　　for i := 2 to 12 do inc(days[i]);
　readln(f, r);

　for i := 1 to 366 do request[i] := nil;

　for i := 1 to r do
　begin
　　readln(f, s);
　　process;
　end;
　for i := 1 to t do readln(f, cost[i]);
　close(f);

　for i := 1 to latest do
　begin
　　p := request[i];
　　while p <> nil do
　　begin
　　　with p^ do pay := cost[gtype] * (d2 - d1 + 1);
　　　p := p^.next;
　　end;
　end;

　k2 := k * 2;
end;

procedure Dynamic;
var i, j, l : integer;
　po, p1, p2, p3 : integer;
　t : longint;
　p : TDay;
　f : text;
　g : array[1..200]of longint;

procedure Sort(l, r : integer);
var
　i, j : byte;
　x, y : longint;
begin
　i := l; j := r; x := g[(l + r) div 2];
　repeat
　　while g[i] > x do i := i + 1;
　　while x > g[j] do j := j - 1;
　　if i <= j then
　　begin
　　　y := g[i]; g[i] := g[j]; g[j] := y;
　　　i := i + 1; j := j - 1;
　　　end;
　　until i > j;
　　if l < j then Sort(l, j);
　　if i < r then Sort(i, r);
　end;

begin
　for i := 0 to latest do new(d[i]);
　d[0]^[1] := 0;
　for i := 2 to k do d[0]^[i] := -1;

　for j := 1 to latest do
　begin
　　p := Request[j];
　　d[j]^ := d[j - 1]^;
　　while p <> nil do
　　begin
　　　with p^ do
　　　begin
　　　　for i := 1 to k do
　　　　begin
　　　　　if d[d1 - 1]^[i] <> -1 then
　　　　　　g[i] := d[d1 - 1]^[i] + pay
　　　　　　else
　　　　　g[i] := -1;
　　　　g[i + k] := d[j]^[i];
　　　end;
　　　sort(1, k2);
　　　p1 := 1;
　　　p3 := 1;
　　　d[j]^[p3] := -1;
　　　while p1 < 2 * k do
　　　begin
　　　　if g[p1] = g[p1 + 1] then inc(p1)
　　　　else
　　　　　begin
　　　　　　d[j]^[p3] := g[p1];
　　　　　　inc(p3);
　　　　　　if p3 > k then break;
　　　　　inc(p1);
　　　　　end;
　　　　end;
　　　　while p3 < k do
　　　　begin
　　　　　inc(p3);
　　　　d[j]^[p3] := -1;
　　　　end;
　　　end;
　　　p := p^.next;
　　end;
　end;
　assign(f, fileout); rewrite(f);
　writeln(f, d[latest]^[k]);
　close(f);
end;

begin
　ti := meml[$40:$6c];

　Initialize;
　Dynamic;

　writeln((meml[$40:$6c] - ti) / 18.2 : 0 : 2)
end.