Audrey 正在规划她在东京度假的第一天！她的第一站是《崩坏：星穹铁道》的快闪店。她从朋友那里听说，日本的火车非常像她最喜欢的列车——星穹列车，因此她决定乘坐一系列火车前往快闪店。碰巧的是，她必须在东京最大的火车站——新宿站进行换乘。

Audrey 计划乘坐到达新宿站的 $n$ 班列车之一，然后换乘从新宿站出发的 $m$ 班列车之一。东京的火车极其准时，Audrey 精确地知道每班列车到达或离开新宿站的时间（精确到秒）。

Audrey 对在新宿站换乘感到有些紧张，因此她不希望换乘时间太紧凑（即换乘时间严格小于 $s$ 秒）。然而，Audrey 也不想在新宿站花太长时间等待换乘。请帮助 Audrey 确定可能的最小换乘时间。Audrey 不会考虑任何跨越自然日分界线的行程。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 50$），分别表示进入和离开新宿站的列车数量。

接下来的 $n$ 行，每行包含一个格式为 HH:MM:SS 的字符串，表示一班进入新宿站的列车的确切到达时间。

接下来的 $m$ 行，每行包含一个格式为 HH:MM:SS 的字符串，表示一班离开新宿站的列车的确切出发时间。

保证每个时间都是合法的时间。具体来说，HH 是介于 $5$ 到 $23$ 之间（含边界）的整数，MM 和 SS 都是介于 $0$ 到 $59$ 之间（含边界）的非负整数。所有数值均使用两位数字表示，可能包含前导零。

最后一行包含一个整数 $s$（$1 \le s \le 600$），表示 Audrey 所需的最小换乘时间（以秒为单位）。

输出格式

输出一个整数，表示 Audrey 进行一次有效换乘所需的最小秒数。如果不存在这样的换乘方案，则输出 -1。

样例

输入样例 1

2 2
10:00:00
11:00:00
10:05:00
11:04:00
300

输出样例 1

300

输入样例 2

1 1
23:13:23
13:23:13
23

输出样例 2

-1