Rain Again 2D
Есенен Турнир по Информатика 2015
Time Limit: 0.2s, Memory Limit: 128MiB
Балконът на Ели е много хубав и Станчо обожава да го наблюдава, докато си говори с нея. Момичето също е много гордо с него, тъй като там има квадратна саксия с размери L на L, в която тя отглежда особено красиви цветя.

Когато завали дъжд, обаче, момичето спира да слуша Станчо и започва да следи с интерес къде в саксията падат капки. Ако в някой момент от началото на дъжда във всеки правоъгълник от саксията със страни, успоредни на стените ѝ, и размери W по абсцисата и H по ординатата е паднала поне по една капка, момичето счита цветята за напоени, зарязва зяпането на дъжда и отново започва да си говори със Станчо. Сега той се е обърнал към вас да определите кога отново Ели ще му обърне внимание.

Предполага се, че горната повърхност на саксията (квадрат с размери L на L) е разположена в координатна система, като върховете ѝ имат координати (0, 0), (0, L), (L, L) и (L, 0). Напишете програма, която определя дали цветята ще бъдат напоени и, ако да, след коя капка ще се случи това.
Вход
От първия ред на стандартния вход се въвеждат целите числа N, L, W, и H, разделени с по един интервал – съответно броят капки, паднали по време на дъжда, дължината на стените на саксията, и дължините на правоъгълника. От всеки от следващите N реда се въвеждат по две цели числа Xi Yi, задаващи координатите на падналите капки, в реда на тяхното падане.
Изход
На единствен ред на стандартния изход изведете едно цяло число – броят капки, които трябва да паднат, преди Ели да счете цветята си за напоени. Ако дори след всички N капки е останал правоъгълник с размери W на H, във вътрешността на който няма паднала нито една капка, изведете -1.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ L ≤ 1,000,000,000
  • 1 ≤ W, HL
  • 0 ≤ Xi, YiL
Примерен Вход Примерен Изход
14 10 5 4 3 4 0 2 5 1 10 10 4 0 8 7 2 7 6 5 9 2 7 3 5 8 6 5 4 2 3 6 13
След падането на 13-тата капка в точка с координати (4, 2), не остава правоъгълник с размери 5 на 4, в който да не е паднала капка.
Мрън!