2540. [Ctsc2000]快乐的蜜月
#2540. [Ctsc2000]快乐的蜜月
题目描述
位于某个旅游胜地的一家宾馆里，有一个房间是总统套房。由于总统套房价格昂贵，因此常常无人光临。宾馆的经理为了创收，决定将总统套房改建为专门为新婚夫妇服务的蜜月房。宾馆经理不仅大幅度降低了蜜月房的价位，而且还对不同身份的顾客制定了不同的价位，以吸引不同身份、不同消费水平的游客。比如对于来订蜜月房的国内来宾、海外旅客、港澳台同胞 等，区别收取费用。
宾馆经理的举措获得了不同凡响的效果。由于蜜月房环境幽雅，服务周到，因此生意红火。宾馆经理在每年年底都会收到第二年的所有蜜月房预订单。每张预订单包括以下几个必要的信息：到达日期、离去日期和顾客身份。
由于宾馆只有一间蜜月房，只能同时接待一对新婚夫妇。因此并不是所有的预订要求都能得到满足。当一些预订要求在时间上发生了重叠的时候，我们就称这些预订要求发生了冲突。
对于那些不与任何其他预订要求发生冲突的预订单，必然会被接受，因为这对宾馆和顾客双方面来说都是件好事。而对于发生冲突的预订要求，宾馆经理则必须拒绝其中的一部分，以保证宾馆有秩序地运转。显然，对于同一时间内发生冲突的预定要求，宾馆经理最多只能接受其中的一个。经理也有可能拒绝同一时间段内的所有预定要求，因为这样可以避免顾客间发生争执。经理在做出决策后，需要将整个计划公布于众，以示公平。这是一个必须慎重的决定，因为它牵涉到诸多方面的因素。经理首先考虑的当然是利润问题。他必然希望获得尽可能多的收入。可是宾馆在获得经济效益的同时，同时也应该兼顾到社会效益 ，不能太惟利是图，还必须照顾到顾客们的感情。如果宾馆经理单从最大获利角度出发来决定接受或拒绝顾客的预订要求的话，就会引起人们的不满。经理有一个学过市场营销学的顾问。顾问告诉经理，可以采取一种折中的做法，放弃牟利最大的方案，而采纳获利第k大的方案。他还通过精确的市场分析，找到了k的最佳取值点，告诉了宾馆经理。
现在请你帮助宾馆经理，从一大堆预订要求中，在上述原则下寻找到获利第k大的方案。宾馆经理将根据此方案来决定接受和拒绝哪些预订要求。
当然，可能有若干种方案的获利是一样大的。这时候，它们同属于获利第i大的方案而不区分看待。例如，假如有3种方案的收入同时为3，有2种方案的收入为2，则收入为3的方案都属于获利最大，收入为2的方案都属于获利第二大。依次类推。
假设所有的住、离店登记都在中午12点进行。
输入格式
输入文件的第一行是两个数，k（1<=k<=100）和t(1<=t<=100)。其中k表示需要选择获利第k大的方案；t表示顾客的身份共划分为t类。
第二行是一个数y，表示下一年的年份。
第三行是一个数r(0<=r<=20000)，表示共有r个预订要求。
以下r行每行是一个预订要求，格式为：
m1/d1 TO m2/d2 id;
其中m1/d1和m2/d2分别表示到达和离去日期。id是一个整数（1<=id<=t），用来标识预订顾客的身份。
最后t行每行为一个整数Pi(1<=i<=t，1<=Pi<=32767)，表示蜜月房对于身份代号为i的顾客的日收费标准。
例：某对顾客于6月1日到达，6月3日离去，对他们的日收费标准为m元/天，则他们共住店两天，需付钱2m元。
输出格式
输出文件仅包含一个整数p，表示在获利第k大的方案下，宾馆的年度总收入额。如果获利第k大的方案不存在，则输出-1。
样例
样例输入
1 1
2000
4
1/1 TO 1/2 1
2/1 TO 2/2 1
3/1 TO 3/2 1
2/28 TO 3/3 1
1
样例输出
6