К очередному Чемпионату Урала было решено подготовить кружки с символикой чемпионата не только для участников, но и для всех желающих.

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала регистрации участников. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до места проведения соревнования, остаётся всего 24 часа.

Заказ на десять миллионов экземпляров кружек (а именно столько заказали организаторы), возможно, не получится увезти за один рейс. Однако за первый рейс хочется привезти максимальное количество кружек.

Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на массу автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до места проведения соревнования вовремя, а этого допустить никак нельзя.

Сколько же кружек можно погрузить в автомобиль, чтобы успеть доставить этот ценный груз за 24 часа, не превысив ограничение на массу автомобиля ни на одной дороге?

В первой строке записаны целые числа N и M — количество узловых пунктов дорожной схемы и количество дорог соответственно (1 ≤ N ≤ 500; 0 ≤ M ≤ N · (N − 1) / 2). В следующих M строках записана информация о дорогах. Каждая дорога описывается в отдельной строке целыми числами a_i, b_i, t_i, m_i, где a_i и b_i — номера узловых пунктов, соединённых i-й дорогой (двигаться по дороге можно в обоих направлениях), t_i — время в минутах, которое тратится на проезд по i-й дороге, m_i — максимальная масса автомобиля в граммах, которому разрешено ехать по i-й дороге (1 ≤ a_i, b_i ≤ N; a_i ≠ b_i; 0 ≤ t_i ≤ 1440; 0 ≤ m_i ≤ 10⁹).

Для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Завод по производству кружек имеет номер 1, а место проведения Чемпионата Урала — номер N. Одна кружка весит 100 грамм, а пустой грузовик — 3000 килограмм (в одном килограмме тысяча грамм).

Выведите одно число — максимальное количество кружек, которое можно привезти за первый рейс, потратив на дорогу не более 24 часов.