Problem: 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 listi in ti 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.

Input

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 listi (listi 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 ti (1 ≤ ti ≤ 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 si (si is a non-empty string of at most 32 characters, consisting of lower case Latin letters), index of the exam day di (1 ≤ di ≤ k), the exam time timei, and sum of money ci (0 ≤ ci ≤ 106, ci — integer) that he's ready to pay for Valera's help. Exam time timei 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.

Output

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.

Examples

Input

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


Output

150
2
1 1 08:16 1 09:29
3 1 10:26 1 10:40


Input

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


Output

3
2
2 1 08:01 1 08:01
1 1 08:02 1 08:03


Input

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


Output

2
1
1 1 08:01 1 08:02

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;

public class E implements Runnable {
	public static void main(String[] args) {
		new E().run();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		boolean eof;
		String buf;

		public FastScanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
			nextToken();
		}

		public FastScanner(InputStream stream) {
			br = new BufferedReader(new InputStreamReader(stream));
			nextToken();
		}

		String nextToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					eof = true;
					break;
				}
			}
			String ret = buf;
			buf = eof ? "-1" : st.nextToken();
			return ret;
		}

		int nextInt() {
			return Integer.parseInt(nextToken());
		}

		long nextLong() {
			return Long.parseLong(nextToken());
		}

		double nextDouble() {
			return Double.parseDouble(nextToken());
		}

		BigInteger nextBigInteger() {
			return new BigInteger(nextToken());
		}

		void close() {
			try {
				br.close();
			} catch (Exception e) {

			}
		}

		boolean isEOF() {
			return eof;
		}
	}

	FastScanner sc;
	PrintWriter out;

	public void run() {
		Locale.setDefault(Locale.US);
		try {
			sc = new FastScanner(System.in);
			out = new PrintWriter(System.out);
			solve();
			sc.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	int nextInt() {
		return sc.nextInt();
	}

	String nextToken() {
		return sc.nextToken();
	}

	long nextLong() {
		return sc.nextLong();
	}

	double nextDouble() {
		return sc.nextDouble();
	}

	BigInteger nextBigInteger() {
		return sc.nextBigInteger();
	}

	int timeToInt(String s) {
		int p = s.indexOf(":");
		int h = Integer.parseInt(s.substring(0, p));
		int m = Integer.parseInt(s.substring(p + 1));
		return h * 60 + m;
	}

	void solve() {
		int m = nextInt();
		int n = nextInt();
		int k = nextInt();
		String[] names = new String[m];
		for (int i = 0; i < names.length; i++) {
			names[i] = nextToken();
		}
		int[] times = new int[m];
		for (int i = 0; i < times.length; i++) {
			times[i] = nextInt();
		}
		HashMap<String, Integer> workNames = new HashMap<String, Integer>();
		for (int i = 0; i < times.length; i++) {
			workNames.put(names[i], times[i]);
		}
		boolean[] busy = new boolean[1440];
		int dayTime = 1440;
		for (int i = 0; i < 4; i++) {
			String[] t = nextToken().split("\\Q-\\E");
			int t1 = timeToInt(t[0]);
			int t2 = timeToInt(t[1]);
			for (int j = t1; j <= t2; j++) {
				busy[j] = true;
				dayTime--;
			}
		}
		Work[] works = new Work[n];
		for (int i = 0; i < n; i++) {
			String name = nextToken();
			int day = nextInt();
			int t = timeToInt(nextToken());
			int e = 0;
			for (int j = 0; j < t; j++) {
				if (!busy[j]) {
					e++;
				}
			}
			int reward = nextInt();
			if (!workNames.containsKey(name)) {
				continue;
			}
			works[i] = new Work(workNames.get(name), (day - 1) * dayTime + e,
					reward, i);
		}
		Arrays.sort(works, new Comparator<Work>() {
			@Override
			public int compare(Work o1, Work o2) {
				if (o1 == null && o2 == null) {
					return 0;
				}
				if (o1 == null) {
					return -1;
				}
				if (o2 == null) {
					return 1;
				}
				return o1.deadLine < o2.deadLine ? -1
						: o1.deadLine > o2.deadLine ? 1 : 0;
			}
		});
		int[][] dp = new int[n + 1][dayTime * k + 1];
		for (int i = 1; i <= n; i++) {
			Work e = works[i - 1];
			if (e == null) {
				for (int j = 0; j < dp[i].length; j++) {
					dp[i][j] = dp[i - 1][j];
				}
				continue;
			}
			dp[i][0] = 0;
			for (int j = 1; j < dp[i].length; j++) {
				dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				if (j >= e.length && j <= e.deadLine) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - e.length]
							+ e.reward);
				}
			}
		}
		out.println(dp[n][dayTime * k]);
		ArrayList<DoneWork> doneWork = new ArrayList<E.DoneWork>();
		for (int i = n, j = dayTime * k; i > 0 && j > 0;) {
			Work e = works[i - 1];
			if (dp[i][j] == dp[i][j - 1]) {
				j--;
			} else if (dp[i][j] == dp[i - 1][j]) {
				i--;
			} else if (e != null && j >= e.length && j <= e.deadLine) {
				if (dp[i][j] == dp[i - 1][j - e.length] + e.reward) {
					doneWork.add(new DoneWork(e.num, j - e.length, j - 1));
					i--;
					j -= e.length;
				}
			} else {
				throw new AssertionError();
			}
		}
		Collections.reverse(doneWork);
		out.println(doneWork.size());
		for (DoneWork e : doneWork) {
			out.println((1 + e.num) + " " + getTime(busy, e.t1, dayTime) + " "
					+ getTime(busy, e.t2, dayTime));
		}
	}

	String getTime(boolean[] busy, int t, int dayTime) {
		return (t / dayTime + 1) + " " + getTime(busy, t % dayTime);
	}

	String getTime(boolean[] busy, int t) {
		t++;
		for (int i = 0; i < busy.length; i++) {
			if (!busy[i]) {
				--t;
				if (t == 0) {
					return getTime(i);
				}
			}
		}
		throw new AssertionError();
	}

	String getTime(int x) {
		int h = x / 60;
		int m = x % 60;
		String s1 = h + "";
		String s2 = m + "";
		if (s1.length() < 2) {
			s1 = "0" + s1;
		}
		if (s2.length() < 2) {
			s2 = "0" + s2;
		}
		return s1 + ":" + s2;
	}

	class DoneWork {
		int num;
		int t1;
		int t2;

		public DoneWork(int num, int t1, int t2) {
			this.num = num;
			this.t1 = t1;
			this.t2 = t2;
		}

	}

	class Work {
		int length;
		int deadLine;
		int reward;
		int num;

		public Work(int length, int deadLine, int reward, int num) {
			this.length = length;
			this.deadLine = deadLine;
			this.reward = reward;
			this.num = num;
		}

	}
}