SPOJ in Gyumri

   Школьник Афанасий решил преуспеть не только в спортивном программировании, но и в спорте. К сожалению, прошло уже много времени со дня его последней тренировки, поэтому, чтобы набрать хорошую форму, придётся начинать с нуля.

   Придумать упражнения для тренировок оказалось непросто, поэтому Афанасий решил поискать идеи в Интернете. Он нашёл сайт, на котором предлагалась несколько серий тренировочных упражнений. Каждая серия тренировок по плану занимает N дней. В каждый из этих N дней предлагается делать одно «упражнение дня», а также к нему прилагаются рекомендации по выполнению в виде «A_i—B_i». Это обозначает, что для повышения уровня силы требуется выполнять упражнение от A_i до B_i раз. Если выполнять упражнение менее, чем A_i, или более, чем B_i раз, то это принесет скорее вред, чем пользу. Афанасий не хочет причинять себе вред, поэтому будет делать от A_i до B_i раз, либо вовсе не делать это упражнение.

   Почитав все описания упражнений, Афанасий понял, что этот курс не рассчитан на новичков, но решил не сдаваться и адаптировать курс упражнений под себя. Он знает, что при изучении i-ого упражнения ему придётся потерять K_i уровней силы, зато за выполнение упражнения X раз его уровень силы возрастёт на F_i*X. Афанасий не может изучить и выполнить упражнение, если его текущий уровень силы меньше K_i. В дни, когда Афанасию не хватает сил или времени упражняться, он может пропускать тренировки, и уровень его силы остаётся без изменения. Зная свои возможности, Афанасий понимает, что если в какой-то день он выполнит упражнение более T раз, то следующие D дней он будет слишком уставшим, чтобы заниматься. Если Афанасий выполнит упражнение более T раз в какой-то из последних D дней серии тренировок, то он начнёт отдыхать со следующего дня, а закончит уже после конца серии.

   Афанасий хочет получить от занятий максимум пользы. Помогите ему определить номер первого упражнения, у которого максимальная величина Fi - количество уровней силы, получаемых за каждый раз выполнения упражнения.

Входные данные.

   Первая строка содержит единственное целое число N (1 ≤ N ≤ 10⁵) – количество дней тренировок.

   Вторая строка содержит два целых числа T, D (1 ≤ T ≤ 10⁶, 1 ≤ D ≤ 10⁵), разделённых единственным пробелом, если в какой-то день Афанасий выполнит упражнение более T раз, то ему придётся отдыхать D следующих дней.

   Следующие N строк описывают упражнения, (i+2)-ая строка содержит описание упражнения в день i. Каждое упражнение описывается числами A_i, B_i, K_i, F_i, (0 ≤ K_i ≤ 10⁹, 1≤ A_i ≤ B_i ≤ 10⁶, 1 ≤ F_i ≤ 10⁶), разделёнными одиночными пробелами, – где A_i, B_i соответственно рекомендуемый минимум и максимум количества раз выполнения упражнения, K_i – количество теряемых уровней силы при изучении упражнения, F_i – количество уровней силы, получаемых за каждый раз выполнения упражнения.

Выходные данные.

   Одно целое число - номер первого упражнения, у которого максимальная величина Fi - количество уровней силы, получаемых за каждый раз выполнения упражнения.

Пример.