E. Помощник
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Невероятно, но в университете ОхВорд началась сессия. Еще более невероятно, что Валера уже успел получить все зачеты «автоматом» и теперь решил подзаработать, решая задачи для своих сокурсников. Он составил список дисциплин list, по которым готов оказать помощь. Пообщавшись с n своими однокурсниками, Валера выяснил про каждого человека следующие данные: какой предмет он сдает, время сдачи предмета и количество денег, которое этот человек готов заплатить за помощь в решении задач.

Располагая такими данными, Валера решил составить расписание, в соответствии с которым он будет решать задачи для своих сокурсников. Естественно, Валерий не может решать задачи круглосуточно, поэтому он определил для себя оптимальный распорядок дня и собирается придерживаться его на протяжении всей сессии. Валера выделил отрезки времени, в течение которых он будет спать, завтракать, обедать и ужинать. Все остальное время юноша может заниматься работой.

Очевидно, что Валера может помочь какому-то студенту только в том случае, если предмет, который будет сдавать этот студент, входит в список list. Вышло так, что у всех студентов, с которыми общался Валера, задания различные, но однотипные, поэтому любое задание по предмету listi Валера может выполнить за ti минут.

Кроме того, начав работать над заданием для какого-либо человека, Валера может лишь прерываться на сон или трапезу и не может переходить к новому заданию, не закончив текущее. Если Валера решил какое-то задание, то он мгновенно может передать по интернету это задание соответствующему студенту.

В случае если этот студент еще не начал сдавать экзамен, то он сможет очень быстро составить шпаргалку, воспользоваться ей, успешно сдать экзамен, и выплатить Валере обещанное вознаграждение. Поскольку времени у Валерия совсем немного, то он попросил вас составить программу, которая найдет последовательность выполнения заданий, приносящую ему наибольшую прибыль.

Входные данные

В первой строке содержатся целые числа m, n, k (1 ≤ m, n ≤ 100, 1 ≤ k ≤ 30) — количество дисциплин в списке list, число потенциальных работодателей Валеры и продолжительность сессии в днях.

В следующих m строках содержатся названия дисциплин listi (listi представляет собой непустую строку длиной не более 32 символов, состоящую из строчных букв латинского алфавита). Гарантируется, что все дисциплины попарно различны.

В (m + 2)-ой строке содержатся m целых чисел ti (1 ≤ ti ≤ 1000) — время в минутах, затрачиваемое Валерой на решение задач по i-ой дисциплине.

Следующие четыре строки содержат отрезки времени, в течение которых Валера спит, завтракает, обедает и ужинает, соответственно. Каждая строка записана в формате H1:M1-H2:M2, где 00 ≤  H1, H2  ≤ 23, 00 ≤  M1, M2  ≤ 59. При этом время H1:M1 соответствует первой минуте какого-то действия Валеры, а время H2:M2 соответствует последней минуте этого действия. Все отрезки времени попарно не пересекаются. Гарантируется, что Валерий ложится спать не раньше полуночи, просыпается раньше, чем начинает завтракать, заканчивает завтракать раньше, чем начинает обедать, заканчивает обедать раньше, чем начинает ужинать и заканчивает ужинать раньше полуночи. Все эти действия длятся меньше суток, но не меньше одной минуты. Время начала и конца каждого действия находятся в пределах одних и тех же суток. Однако при этом возможна ситуация, что у Валеры не окажется свободного времени для выполнения заданий.

Далее следуют n строк, содержащих описание студентов. Про каждого студента известна дисциплина si (si представляет собой непустую строку длиной не более 32 символов, состоящую из строчных букв латинского алфавита), по которой ему предстоит сдавать экзамен, номер дня di (1 ≤ di ≤ k), время сдачи timei, и сумма денег ci (0 ≤ ci ≤ 106, ci — целое), которую он готов заплатить за Валерину помощь. Время сдачи экзамена timei задается в формате HH:MM, где 00 ≤  HH  ≤ 23, 00 ≤  MM  ≤ 59. Валера получит вознаграждение в том случае, если он закончит выполнять задание строго раньше начала экзамена соответствующего студента.

Выходные данные

В первую строку выведите наибольшую прибыль, которую сможет получить Валерий. Во второй строке должно содержаться число p — количество заданий, которые Валера должен выполнить. Далее в p строках выведите последовательность их выполнения в хронологическом порядке в следующем формате: номер студента, которому Валера должен помочь; номер дня, в который Валера должен начать выполнять задание; время, в которое Валера должен начать выполнять задание (первая минута работы); номер дня, в который Валера должен закончить выполнять задание; время, в которое Валера должен закончить выполнять задание (последняя минута работы). Для уточнения формата вывода изучите примеры из условия.

Примеры
Входные данные
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
Выходные данные
150
2
1 1 08:16 1 09:29
3 1 10:26 1 10:40
Входные данные
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
Выходные данные
3
2
2 1 08:01 1 08:01
1 1 08:02 1 08:03
Входные данные
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
Выходные данные
2
1
1 1 08:01 1 08:02