27209번 - Airport 서브태스크다국어

In EGOI Airport, there are $N$ runways, numbered from $1$ to $N$. In this airport, for an airplane, it takes $K$ minutes to take off, and $L$ minutes to land. During a takeoff or landing of an airplane, a runway is occupied by the airplane for a duration of $K$ or $L$ minutes.

JOI-kun is working at EGOI Airport. His job is to arrange the schedule of takeoffs and landings for a contiguous time slot of $T$ minutes. The beginning of the time slot is time $0$. The time when $t$ minutes passed after the beginning of the time slot is time $t$. The end of the time slot is time $T$.

In the time slot, $M$ airplanes will arrive at EGOI Airport. They are numbered from $1$ to $M$. The ($1 ≤ i ≤ M$) will start landing at time $A_i$. But the runway used by airplane $i$ is not yet fixed. It will be fixed by JOI-kun. The schedule for the takeoffs is not fixed at all. JOI-kun will decide the number of airplanes which will take off, the time of a takeoff of each airplane, and the runway used by it.

In summary, the schedule has to obey the following rules.

• It is not allowed that more than one airplane take off or land at the same time in the same runway. However, it is allowed that an airplane starts taking off or landing, just after another airplane finished taking off or landing in the same runway.
• All takeoffs and landings should be finished in the time slot of $T$ minutes. Namely, it is not allowed for an airplane to start taking off or landing before time $0$. It is not allowed for an airplane to finish taking off or landing after time $T$.

JOI-kun wants to arrange the schedule so that it obeys the above rules, and the number of airplanes which will take off is maximized.

Write a program which, given the number of runways, the number of airplanes which will land, the length of the time slot, the time required for a takeoff, the time required for a landing, and the time when each airplane will start landing, calculates the maximum possible number of airplanes which will take off from EGOI Airport. If it is not possible to arrange the schedule so that it obeys the rules, your program should report it.

Read the following data from the standard input. Given values are all integers.

$N$ $M$ $T$ $K$ $L$

$A_1$ $A_2$ $\cdots$ $A_M$

Write one line to the standard output. The output should contain the maximum possible number of airplanes which will take off from EGOI Airport. If it is not possible to arrange the schedule so that it obeys the rules, output -1.

• $1 ≤ N ≤ 100\,000$.
• $1 ≤ M ≤ 100\,000$.
• $1 ≤ T ≤ 1\,000\,000\,000 (= 10^9)$.
• $1 ≤ K ≤ T$.
• $1 ≤ L ≤ T$.
• $0 ≤ A_i ≤ T - L$ ($1 ≤ i ≤ M$).