CF33E.Helper

It's unbelievable, but an exam period has started at the OhWord University. It's even more unbelievable, that Valera got all the tests before the exam period for excellent work during the term. As now he's free, he wants to earn money by solving problems for his groupmates. He's made a list of subjects that he can help with. Having spoken with n of his groupmates, Valera found out the following information about them: what subject each of them passes, time of the exam and sum of money that each person is ready to pay for Valera's help.

Having this data, Valera's decided to draw up a timetable, according to which he will solve problems for his groupmates. For sure, Valera can't solve problems round the clock, that's why he's found for himself an optimum order of day and plans to stick to it during the whole exam period. Valera assigned time segments for sleep, breakfast, lunch and dinner. The rest of the time he can work.

Obviously, Valera can help a student with some subject, only if this subject is on the list. It happened, that all the students, to whom Valera spoke, have different, but one-type problems, that's why Valera can solve any problem of subject list__i in t__i minutes.

Moreover, if Valera starts working at some problem, he can break off only for sleep or meals, but he can't start a new problem, not having finished the current one. Having solved the problem, Valera can send it instantly to the corresponding student via the Internet.

If this student's exam hasn't started yet, he can make a crib, use it to pass the exam successfully, and pay Valera the promised sum. Since Valera has little time, he asks you to write a program that finds the order of solving problems, which can bring Valera maximum profit.

令人难以置信，OhWord大学的考试周已经开始了。更令人难以置信的是，瓦列拉因学期中表现优异，早已在考试周开始前就拿到了全部科目的考试卷。如今他空闲下来，便打算通过为同班同学解题来赚钱。他已列出一份自己能够辅导的科目清单。瓦列拉与他的 $ n $ 位同班同学进行了沟通，从而获得了如下信息：每位同学所考的科目、考试时间，以及每人愿意为瓦列拉的帮助所支付的金额。

基于这些数据，瓦列拉决定制定一份时间表，用以安排他为同学们解题的工作顺序。当然，瓦列拉不可能全天候工作，因此他为自己规划了一天中最优的时间安排，并计划在整个考试周内严格遵守。瓦列拉已为睡眠、早餐、午餐和晚餐分别划定了固定的时间段；其余时间则可用于工作。

显然，瓦列拉仅能帮助那些所考科目出现在他的科目清单中的同学。巧合的是，所有与瓦列拉沟通过的同学，其题目虽然各不相同，但均属于同一类型——因此，瓦列拉求解清单中第 $ i $ 个科目（记为 $\text{list}_i$）的任意一道题所需时间为 $ t_i $ 分钟。

此外，一旦瓦列拉开始解答某道题目，他仅能在睡眠或进餐时中断；他不能在未完成当前题目时就着手解答新题。题目解答完毕后，瓦列拉可立即通过互联网将答案发送给对应的同学。

若该同学的考试尚未开始，他便可利用这份“小抄”顺利通过考试，并向瓦列拉支付事先承诺的酬金。由于瓦列拉时间紧迫，他请你编写一个程序，找出一种解题顺序，使得瓦列拉获得的总收益最大。

The first line contains integers m, n, k (1 ≤ m, n ≤ 100, 1 ≤ k ≤ 30) — amount of subjects on the list, amount of Valera's potential employers and the duration of the exam period in days.

The following m lines contain the names of subjects list__i (list__i is a non-empty string of at most 32 characters, consisting of lower case Latin letters). It's guaranteed that no two subjects are the same.

The (m + 2)-th line contains m integers t__i (1 ≤ t__i ≤ 1000) — time in minutes that Valera spends to solve problems of the i-th subject. Then follow four lines, containing time segments for sleep, breakfast, lunch and dinner correspondingly.

Each line is in format H1:M1-H2:M2, where 00 ≤  H1, H2  ≤ 23, 00 ≤  M1, M2  ≤ 59. Time H1:M1 stands for the first minute of some Valera's action, and time H2:M2 stands for the last minute of this action. No two time segments cross. It's guaranteed that Valera goes to bed before midnight, gets up earlier than he has breakfast, finishes his breakfast before lunch, finishes his lunch before dinner, and finishes his dinner before midnight. All these actions last less than a day, but not less than one minute. Time of the beginning and time of the ending of each action are within one and the same day. But it's possible that Valera has no time for solving problems.

Then follow n lines, each containing the description of students. For each student the following is known: his exam subject s__i (s__i is a non-empty string of at most 32 characters, consisting of lower case Latin letters), index of the exam day d__i (1 ≤ d__i ≤ k), the exam time time__i, and sum of money c__i (0 ≤ c__i ≤ 106, c__i — integer) that he's ready to pay for Valera's help. Exam time time__i is in the format HH:MM, where 00 ≤  HH  ≤ 23, 00 ≤  MM  ≤ 59. Valera will get money, if he finishes to solve the problem strictly before the corresponding student's exam begins.

第一行包含三个整数 $m$、$n$、$k$（$1 \le m, n \le 100$，$1 \le k \le 30$）—— 分别表示科目列表中的科目数量、Valera 潜在雇主的数量，以及考试期的持续天数（以天为单位）。

接下来的 $m$ 行每行包含一个科目名称 $\text{list}_i$（$\text{list}_i$ 是一个非空字符串，长度至多为 32，仅由小写拉丁字母组成）。保证任意两个科目名称互不相同。

第 $(m+2)$ 行包含 $m$ 个整数 $t_i$（$1 \le t_i \le 1000$）—— 表示 Valera 解决第 $i$ 门科目习题所需的时间（单位：分钟）。随后四行分别给出睡眠、早餐、午餐和晚餐的时间区间。

每行格式为 H1:M1-H2:M2，其中 $00 \le H1, H2 \le 23$，$00 \le M1, M2 \le 59$。时间 H1:M1 表示 Valera 开始某项活动的第一分钟，H2:M2 表示该活动结束的最后一分钟。任意两个时间区间互不重叠。保证 Valera 在午夜之前入睡，起床时间早于早餐开始时间，早餐结束时间早于午餐开始时间，午餐结束时间早于晚餐开始时间，且晚餐结束时间早于午夜。所有这些活动持续时间均小于一整天，但不少于一分钟；且每项活动的起始与结束时间均落在同一天内。但有可能 Valera 完全没有可用于解题的时间。

接下来是 $n$ 行，每行描述一位学生。对每位学生，已知以下信息：其考试科目 $s_i$（$s_i$ 是一个非空字符串，长度至多为 32，仅由小写拉丁字母组成）、考试日期索引 $d_i$（$1 \le d_i \le k$）、考试时间 $\text{time}_i$，以及他愿意为 Valera 的帮助所支付的金额 $c_i$（$0 \le c_i \le 10^6$，$c_i$ 为整数）。考试时间 $\text{time}_i$ 的格式为 HH:MM，其中 $00 \le HH \le 23$，$00 \le MM \le 59$。若 Valera 在对应学生的考试开始前严格更早完成解题，则他可获得这笔钱。

In the first line output the maximum profit that Valera can get. The second line should contain number p — amount of problems that Valera is to solve. In the following p lines output the order of solving problems in chronological order in the following format: index of a student, to whom Valera is to help; index of the time, when Valera should start the problem; time, when Valera should start the problem (the first minute of his work); index of the day, when Valera should finish the problem; time, when Valera should finish the problem (the last minute of his work). To understand the output format better, study the sample tests.

第一行输出 Valera 能获得的最大利润。
第二行输出一个整数 $p$ —— Valera 需要解决的问题数量。
接下来的 $p$ 行按时间顺序输出问题的解决顺序，每行格式如下：
帮助的学生编号；
Valera 应开始该问题的时间编号；
Valera 应开始该问题的具体时刻（即其工作的第一分钟）；
Valera 应完成该问题的日期编号；
Valera 应完成该问题的具体时刻（即其工作的最后一分钟）。
为更好地理解输出格式，请参考样例测试。