Ви отримали замовлення на доставку 10000000 чашок для учасників олімпіади, які необхідно доставити до місця призначення не пізніше ніж за 24 години. У вас є автомобіль, який може вмістити довільну кількість чашок.
Але на деяких дорогах країни, є обмеження на вагу транспортного засобу.

Яку максимально можливу кількість чашок можна перевезти за одну поїздку автомобілем так, щоб вкластись в термін 24 години?

Формат вхідних даних

В першому рядку два цілих числа \(N,M\) - кількість міст та доріг. (\(1 \le N \le 500\)).
В наступних \(M\) рядках знаходиться по чотири цілих числа - інформація про дороги: номера міст, які з'єднані дорогою, час проїзду дорогою, і максимальна вага автомобіля, якаму дозволено рухатись цією дорогою.
Всі дороги з'єднують різні пункти. Для кожної пари міст є не більше ніж 1 дорога.

Стартове місто має номер \(1\), фінішне має номер \(N\). Час проїзду дорогою заданий в хвилинах, і не перевищує 1440. Обмеження на масу задано в грамах, і не перевищує 1000000000. Крім того відомо, зо 1 чашка важить 100 грам, а пустий автомобіль 3 тони.

Формат вихідних даних

Виведіть єдине число - максимальну кількість чашок які можна провезти за один рейс, витратив не більше ніж 24 години

Приклад вхідних даних-1

3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099

Приклад вихідних даних-1

2