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

1741. Монстр общения

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
После возвращения из летнего лагеря мальчик Коля стал настоящим «монстром общения». Он проводит в интернете всё свободное время, общаясь с друзьями по ICQ. Но совсем недавно протокол этого сервиса был в очередной раз изменён, и клиент Коли перестал работать. Теперь, для того чтобы общаться с друзьями дальше, ему необходимо обновить свой клиент с версии 1 до версии n.
В интернете Коля нашёл m обновлений, i-е из которых обновляет клиент с версии xi до yi и имеет размер di мегабайт. Каждое обновление устанавливается только на соответствующую версию клиента, но ни на какую более раннюю или более позднюю версию.
Первая версия клиента, имеющаяся у Коли — лицензионная, а многие из найденных им обновлений являются пиратскими. После установки пиратского обновления клиент всегда будет пиратским, вне зависимости от обновлений, которые будут устанавливаться после этого. Среди остальных обновлений имеются как лицензионные, которые можно устанавливать на пиратскую версию клиента, так и лицензионные, которые этого не допускают. Пиратские обновления можно ставить как на лицензионную, так и на пиратскую версию клиента.
Коля уже очень соскучился по друзьям, поэтому он хочет как можно быстрее скачать нужные обновления, а интернет у него совсем не быстрый. Помогите ему определить минимальный суммарный объём трафика, который нужно потратить для обновления клиента с версии 1 до n. Стоит отметить, что Коле не важно, будет ли клиент версии n лицензионным.

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

В первой строке через пробел записаны целые числа n и m (2 ≤ n ≤ 104; 1 ≤ m ≤ 104).
Каждая из следующих m строк содержит описание одного обновления в формате «xi yi di si», где si — тип обновления: «Pirated» — пиратское, «Cracked» — лицензионное, которое ставится на пиратскую версию, «Licensed» — лицензионное, которое не ставится на пиратскую версию, а числа xi, yi, di означают, что обновление устанавливается на клиент версии xi, обновляет его до версии yi и имеет размер di мегабайт (1 ≤ xi < yi ≤ n; 1 ≤ di ≤ 106). Данные в каждой строке разделены ровно одним пробелом.

Результат

Если у Коли получится успешно обновить клиент с версии 1 до версии n, в первой строке выведите «Online», а во второй — минимальный суммарный объём входящего трафика, необходимый для обновления.
Если же обновить клиент не получится, выведите «Offline».

Примеры

исходные данныерезультат
3 4
1 3 10 Licensed
1 2 2 Pirated
2 3 3 Licensed
2 3 6 Cracked
Online
8
3 1
1 2 10 Licensed
Offline
Автор задачи: Алексей Самсонов (подготовка — Марина Мухачёва)
Источник задачи: XIV Открытый командный чемпионат УрГУ по программированию