DVD
Petya has a new computer game, and his friends have asked him to make copies of it on blank DVD discs. He promised them that everything would be ready in M + 1 seconds. However, Petya realized that due to ongoing renovations in his house, there will be power outages, which might prevent him from completing the task on time. Petya's friends trust him to be responsible, so they will be disappointed if he fails to deliver as promised.
The game takes up the entire space on a single DVD disc. Petya's drive, called StrangeDVD, supports recording speeds of 4x, 8x, and 16x. However, the speed definitions on StrangeDVD differ from the standard. Assume that the drive tray opens and closes instantly, and Petya can insert and remove discs instantly as well, meaning the only time spent is on the actual recording. The StrangeDVD drive does not support multisession recording, so each disc must be recorded in one go.
The quality of the recorded disc depends on the speed: at 16x, the quality is 1; at 8x, the quality is 2; and at 4x, the quality is 3. Petya needs to maximize the total quality of the discs, and if there are multiple ways to achieve this, he should choose the option that minimizes the time spent.
Power outages are not coordinated and may overlap. If the power is already out when another outage is scheduled, the second outage does not affect the situation. For example, if outages are planned from the 1st to the 10th second, from the 5th to the 20th, and from the 15th to the 30th, the power goes out at the 1st second, stays out through the 5th, comes back on at the 11th, goes out again at the 15th, and returns at the 31st. No two teams will turn off the power simultaneously. The time starts at zero seconds, and Petya has a total of M + 1 seconds (0, 1, ..., M).
Input
The input consists of the number M (the last second Petya has), N (the number of discs to be recorded), Q (the time in seconds to record one disc at 16x; at 8x it takes 2Q, and at 4x it takes 4Q), and K (the number of power outages). This is followed by K pairs of numbers P1, P2 indicating the start and end of each outage. These pairs are not necessarily in chronological order, but always P1 ≤ P2. All numbers are separated by spaces.
0 ≤ M, N, P1_{i}, P2_{i} ≤ 2,000,000,000, 1 ≤ Q ≤ 500,000,000 (or 1 ≤ 4Q ≤ 2,000,000,000), 0 ≤ K ≤ 10,000.
Output
Output -1 if Petya cannot finish recording all the discs in time. If he can, output the last second he spends on recording and the total quality achieved, separated by a space.