Улсын олимпиадын сорил №1. Бодлого J

Колягийн мессенжерийн програм нь хуучирснаас найзуудтайгаа чатлаж чадахаа байжээ. Одоо чатлахын тулд програмаа 1.0 гэсэн хувилбараас n.0 хувилбар хүртэл шинэчлэх хэрэгтэй болсон байна.
Интернетэд уг програмын m ширхэг суулгац олдсон ба i-р суулгац нь програмыг x_i-р хувилбараас y_i хувилбартай болгож шинэчлэх ба d_i мегабайт хэмжээтэй байна. Суулгац бүр нь зөвхөн харгалзах хувилбартай програм дээрээ суудаг ба түүнээс эртний болон сүүлийн үеийн хувилбар дээр суухгүй.
Коляд байгаа эхний хувилбар нь лицензтэй хувилбар ба олдсон m суулгацуудын зарим нь хулгайнх байна. Хулгайн суулгацаар шинэчлэгдсэнээс хойш програм нь хулгайнх болж хувирах ба дараа нь лицензтэй хувилбараар шинэчилсэн ч хулгайнх хэвээр үлдэнэ. Мөн зарим лицензтэй суулгацууд нь зөвхөн лицензтэй програм дээр суух бол зарим нь хулгайн програм дээр ч сууж чадна. Хулгайн суулгацыг хулгайн програм дээр ч лицензтэй програм дээр ч суулгаж болно.
Колягийн програмыг 1.0 хувилбараас n.0 хувилбар болтол шинэчлэхэд татаж авах шаардлагатай файлын хэмжээний хамгийн бага утгыг ол. n.0 хувилбар нь хулгайнх байх эсэх нь хамаагүй.

Оролт
Эхний мөрөнд n, m бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө. (2 ≤ n ≤ 10₄; 1 ≤ m ≤ 10₄).

Дараагийн m ширхэг мөрөнд «x_i y_i d_i s_i» хэлбэрээр суулгацуудыг тодорхойлно.
Энд s_i нь суулгацын төрөл юм: «Pirated» — хулгайн, «Cracked» — хулгайн програм дээр сууж чадах лицензтэй суулгац, «Licensed» — хулгайн програм дээр сууж чаддаггүй лицензтэй суулгац. x_i y_i d_i тоонуудын тайлбар бодлогын өгүүлбэрт байгаа (1 ≤ x_i < y_i ≤ n; 1 ≤ d_i ≤ 10⁶).

Гаралт
Хэрэв Колягийн програмыг n.0 хувилбар хүртэл шинэчлэх боломжтой бол эхний мөрөнд "Online" гэсэн үгийг, хоёр дахь мөрөнд татаж авах файлуудын нийт хэмжээний хамгийн бага утгыг хэвлэнэ.
Хэрэв ийм боломжгүй бол "Offline" гэсэн үгийг хэвлэнэ.

Жишээ оролт 1
3 4
1 3 10 Licensed
1 2 2 Pirated
2 3 3 Licensed
2 3 6 Cracked

Жишээ гаралт 1
Online
8

Жишээ оролт 2
3 1
1 2 10 Licensed

Жишээ гаралт 2
Offline