Agent Maria's Subway Mission

Agent Maria has been sent on a dangerous mission in city S. She must take the only subway line in the city. The subway has n stations (numbered 1 to n). The trains run in two directions: forward trains run from station 1 to station n and backward trains run from station n to station 1. For any two consecutive stations, the travel time is fixed at t units and station dwell times are negligible.

At time 0, Maria starts at station 1. She must meet her contact at station n exactly by time T. However, due to pursuing agents she wants to minimize the total time spent waiting on platforms. (Note that if she arrives earlier than T at station n, the extra waiting time at the destination is also counted.)

A forward train with departure time d (given in the input) departs station 1 at time d and reaches station i at time d+(i-1)\(t\) (i.e. the time for station 1 is d, station 2 is d+t, ..., station n is d+(n-1)t). Similarly, a backward train with departure time d departs from station n at time d and reaches station i at time d+(n-i)\(t\).

Maria may ride any train provided that she is present at that station at or before the train’s departure time. She can transfer between trains instantly if two trains are at the same station at the same time. However, whenever she waits at a station (i.e. the time gap between her arrival and the train she boards), that waiting time is counted toward her total waiting time. Her goal is to plan a journey from station 1 (at time 0) to station n such that she arrives no later than time T and the sum of all waiting times (including any waiting at station n upon arriving early) is minimized.

Input details are given below. Write a program to compute the minimum total waiting time. If it is impossible for Maria to reach station n by time T, output -1.

inputFormat

The input is given in the following format:

 n T t m
 d1 d2 ... dm
 k
 d'1 d'2 ... d'k

Where:

• n is the number of stations (2 ≤ n ≤ 100, say).
• T is the meeting time at station n (T is a nonnegative integer).
• t is the fixed travel time between consecutive stations (a positive integer).
• m is the number of forward trains. Then follow m integers, each denoting a departure time from station 1 for a forward train.
• k is the number of backward trains. Then follow k integers, each denoting a departure time from station n for a backward train.

All times are nonnegative integers. You may assume that the trains in each list are given in non-decreasing order.

outputFormat

Output a single integer: the minimum total waiting time needed for Maria to reach station n at or before time T. If it is impossible, output -1.

sample

5 30 5 2
0 3
2
5 6

10