ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2005 Тур I

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Транспортировка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
К очередному Чемпионату Урала было решено подготовить кружки с символикой чемпионата не только для участников, но и для всех желающих.
Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала регистрации участников. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до места проведения соревнования, остаётся всего 24 часа.
Заказ на десять миллионов экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек.
Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до места проведения соревнования вовремя, а этого допустить никак нельзя.
Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

Исходные данные

В первой строке находятся числа N (1 ≤ N ≤ 500) и M — количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих M строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой. Потом время, которое тратится на проезд по этой дороге. И, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.
Узловые пункты нумеруются числами от 1 до N. При этом завод по производству кружек имеет номер 1, а место проведения Чемпионата Урала — номер N. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик — 3 тонны.

Результат

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

Пример

исходные данныерезультат
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
2
Автор задачи: Павел Егоров
Источник задачи: IX Чемпионат Урала по программированию. Екатеринбург, УрГУ, 19-24 апреля 2005г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1379. Транспортировка