Kolya has returned from a summer camp and now he's a real communication
fiend. He spends all his free time on the Web chatting with his friends via
ICQ. However, lately the protocol of this service was changed once again, and
Kolya's client stopped working. Now, in order to communicate with his friends
again, Kolya has to upgrade his client from version 1 to version n.
Kolya has found m upgrade programs on the Web. The i-th program upgrades
the client from version xi to version yi and its size is di megabytes. Each
program can be installed on the corresponding version of the client only; it
can't be installed on either earlier or later versions.
The first version, which is currently installed on Kolya's computer, is
licensed, and many of the upgrade programs are pirate copies. If a pirate
upgrade program is used, the client will always be pirated after that, whatever
upgrade is used later. Some of the licensed upgrade programs can be installed
on a pirate version of the client, and some of them can't. All the pirate
upgrade programs can be installed on both licensed and pirate versions of the
Kolya is missing his friends very much, so he wants to download the necessary
upgrade programs as soon as possible. Unfortunately, his Web connection is not
very fast. Help Kolya determine the minimal total traffic volume necessary for
upgrading the client from version 1 to version n. Kolya doesn't care if the
final version n of his client is licensed or not.
The first line contains space-separated integers n and m (2 ≤ n ≤ 104; 1 ≤ m ≤ 104).
Each of the following m lines describes one upgrade program in the form
“xi yi di si”. Here, si is the type of the program: “Pirated”,
“Cracked”, or “Licensed”. A cracked upgrade program is a licensed program
that can be installed on a pirate version of the client, and a licensed program
can't be installed on a pirate version. The numbers xi and yi mean that
the program is installed on version xi of the client and upgrades it to
version yi. The number di is the size of the program in megabytes (1 ≤ xi < yi ≤ n; 1 ≤ di ≤ 106). The data
in each line are separated with exactly one space.
If Kolya can upgrade the client from version 1 to version n,
output “Online” in the first line and the minimal necessary total incoming
traffic volume in the second line.
If it is impossible to upgrade the client, output “Offline”.
1 3 10 Licensed
1 2 2 Pirated
2 3 3 Licensed
2 3 6 Cracked
1 2 10 Licensed
Problem Author: Alex Samsonov (prepared by Marina Mukhacheva)
Problem Source: XIV Open USU Championship