Ferry Schedule

Time limit1sMemory limit128 MB

Summary

Given ferry travel time, turnaround preparation time, and fixed departure lists for both towns, compute the minimum number of ferries required to cover every scheduled trip.

Level: Medium6 of 10
Topics: Greedy, Simulation, Sorting
Solved: No attempts yet

Problem

Towns A and B are connected by a ferry route.

You are given the travel time for one ferry trip, the minimum preparation time needed before the ferry can board passengers for its next trip, and the scheduled departure times from both towns.

Find the minimum number of ferries needed to operate every scheduled departure.

A ferry may travel only at one of the scheduled departure times. It cannot be moved at an unscheduled time.

Input

The first line contains two integers K and L separated by a space: the travel time between the two towns and the minimum preparation time, in minutes.

The next line contains an integer A, the number of departures from town A. The following A lines each contain one departure time from town A.

The next line contains an integer B, the number of departures from town B. The following B lines each contain one departure time from town B.

The constraints are 1 <= K, L <= 1000 and 1 <= A, B <= 1440.

All departure times for each town are given in chronological order and written in HH:MM format. If the hour or minute has one digit, it is written with a leading zero.

All times are between 00:00 and 23:59.

Output

Print one integer: the minimum number of ferries needed to operate the schedule.

Examples3

Example 1
Input
```
30 15
1
08:00
1
08:00
```
Expected output
```
2
```
Example 2
Input
```
15 30
2
08:00
12:00
1
08:45
```
Expected output
```
1
```

Example 3

Input

Expected output