难以置信,OhWord 大学已经开始考试了。更令人难以置信的是,瓦莱拉在学期中表现出色,在考试前就通过了所有测试。现在他自由了,他想通过为队友解决问题来赚钱。他列出了他可以提供帮助的科目清单。在与他的n个队友交谈后,瓦莱拉找到了关于他们的以下信息:他们每个人通过了什么科目,考试时间以及每个人准备为瓦莱拉的帮助支付的金额。
有了这些数据,瓦莱拉决定制定一个时间表,根据这个时间表他将为队友解决问题。当然,瓦莱拉不可能全天候解决问题,这就是为什么他为自己找到了最佳的日程安排,并计划在整个考试期间坚持下去。瓦莱拉分配了睡眠、早餐、午餐和晚餐的时间段。其余时间他可以工作。
显然,Valera 可以帮助学生学习某些科目,前提是该科目在列表中。碰巧,瓦莱拉与之交谈的所有学生都有不同但单一类型的问题,这就是为什么瓦莱拉可以在几分钟内解决主题列表的任何问题。
此外,如果瓦莱拉开始解决某个问题,他只能停下来睡觉或吃饭,但在没有完成当前问题的情况下,他不能开始新的问题。解决问题后,瓦莱拉可以立即通过互联网将其发送给相应的学生。
如果该学生的考试尚未开始,他可以制作一个婴儿床,用它来成功通过考试,并向瓦莱拉支付承诺的金额。由于瓦莱拉的时间很少,他要求你编写一个程序,找到解决问题的顺序,这可以给瓦莱拉带来最大的利润。
输入
第一行包含整数 m、n、k (1 ≤ m, n ≤ 100, 1 ≤ k ≤ 30) — 列表中的科目数量、Valera 潜在雇主的数量以及考试持续时间(以天为单位)。
接下来的m行包含listi的主题名称(listi是一个最多32个字符的非空字符串,由小写拉丁字母组成)。保证没有两个主题是相同的。
第 (m + 2) 行包含 m 个整数 ti (1 ≤ ti ≤ 1000) — Valera 解决第 i 个科目的问题所花费的时间(以分钟为单位)。然后按照四行,分别包含睡眠、早餐、午餐和晚餐的时间段。
每行的格式为 H1:M1-H2:M2,其中 00 ≤ H1、H2 ≤ 23、00 ≤ M1、M2 ≤ 59。时间 H1:M1 代表 Valera 某个动作的第一分钟,时间 H2:M2 代表该动作的最后一分钟。两个时间段没有交叉。保证 Valera 在午夜之前睡觉,在吃早餐之前起床,在午餐之前吃完早餐,在晚餐之前吃完午餐,在午夜之前吃完晚餐。所有这些动作持续的时间不到一天,但也不少于一分钟。每个动作的开始时间和结束时间都在同一天内。但瓦莱拉可能没有时间解决问题。
然后n行,每行包含学生的描述。对于每个学生,以下信息是已知的:他的考试科目 si(si 是最多 32 个字符的非空字符串,由小写拉丁字母组成)、考试日期索引 di (1 ≤ di ≤ k)、考试时间 timei 以及他准备支付 Valera 帮助的金额 ci (0 ≤ ci ≤ 106,ci — 整数)。考试时间 timei 的格式为 HH:MM,其中 00 ≤ HH ≤ 23、00 ≤ MM ≤ 59。如果 Valera 在相应学生考试开始之前严格完成问题,他将获得金钱。
输出
第一行输出 Valera 可以获得的最大利润。第二行应包含数字 p——Valera 要解决的问题数量。在下面的 p 行中,按时间顺序输出解决问题的顺序,格式如下: Valera 要帮助的学生的索引;时间索引,Valera 何时应该开始解决问题;时间,瓦莱拉应该开始解决问题的时间(他工作的第一分钟);当天的索引,瓦莱拉应该完成问题的时间;时间,瓦莱拉应该完成问题的时间(他工作的最后一分钟)。为了更好地理解输出格式,请研究示例测试。
示例
输入 #1
3 3 4 calculus algebra history 58 23 15 00:00-08:15 08:20-08:35 09:30-10:25 19:00-19:45 calculus 1 09:36 100 english 4 21:15 5000 history 1 19:50 50
输出 #1
150 2 1 1 08:16 1 09:29 3 1 10:26 1 10:40
输入 #2
2 2 1 matan codeforces 1 2 00:00-08:00 09:00-09:00 12:00-12:00 18:00-18:00 codeforces 1 08:04 2 matan 1 08:02 1
输出 #2
3 2 2 1 08:01 1 08:01 1 1 08:02 1 08:03
输入 #3
2 2 1 matan codeforces 2 2 00:00-08:00 09:00-09:00 12:00-12:00 18:00-18:00 codeforces 1 08:04 2 matan 1 08:03 1
输出 #3
2 1 1 1 08:01 1 08:02