ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1689. Fisherman and Barbell

Time limit: 1.0 second
Memory limit: 64 MB
Problem illustration
Fisherman Ivan likes to practice weightlifting when he is free from fishing. He lifts the barbell, turns, twists, and spins it, and does everything he wants with it. During these tricks the special semicircular groove in which the barbell is usually kept stays free and worms crawl into it. Ivan doesn't want to squash the worms because he will need them as a bait for fishing. That is why he chooses the place to put the barbell in such way that it hurts as few worms as possible. Can you find such a place?
There is a p cm wide plate on each side of the barbell. The distance between the left edge of the left plate and the right edge of the right plate is b cm. The length of the groove is g cm. All worms have the same length w cm and lie along the groove on its bottom without overlapping. If even a small part of a worm gets under a plate of the barbell, it is considered squashed and is unfit for fishing.


In the first line you are given the length of the groove g and the length of a worm w (1 ≤ wg ≤ 100000). In the second line there are the characteristics of the barbell b and p (1 ≤ pb/2 ≤ g/2). The third line contains the number of worms n (1 ≤ n ≤ 100000). In the fourth line you are given the coordinates of the worms xi separated with a space; they are in the range from 0 to g − w. The coordinate of a worm is the distance from its left end to the left end of the groove in centimeters.
All numbers in the input data are integers.


Output the integer distance from the left edge of the left plate of the barbell to the left end of the groove in centimeters. The barbell should hurt the minimal number of worms. In the case of equal number of the hurt worms, the distance to the left end of the groove should be minimal.


1000 4
500 60
47 68 22 237 585 417 666 996 888 555
20 1
2 1
1 2 3 4 6 8 10 12 14 16 19
Problem Author: Stanislav Vasilyev
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)