DVD

Petya has a new computer game, and his friends brought him blank DVD discs, asking him to make copies of the game. Petya promised that everything would be ready in M+1 seconds. However, as soon as Petya started recording the first disc, he remembered there were ongoing renovations at his home, and there will be power outages, which could prevent him from finishing in time. Petya's friends consider him responsible, so they will be upset if he does not finish on time.

The game takes up all the free space of a single DVD disc. Petya's drive, called StrangeDVD, supports writing at speeds of $4\text{X}$, $8\text{X}$, and $16\text{X}$, but here the value of $X$ may be different from the standard — for example, $4\text{X}$ on the StrangeDVD drive may not match $4\text{X}$ on other drives. Assume the drive tray opens and closes instantly, and Petya can instantly remove and insert discs, so the only time spent is on actual recording. The drive does not support multisession, so each disc must be recorded in one uninterrupted session.

Recording at $16\text{X}$ results in quality $1$; at $8\text{X}$ — quality $2$; at $4\text{X}$ — quality $3$. Determine how much time Petya will spend recording the discs so that the total quality is maximized, and if there are several ways, the spent time is minimized.

Power outages are not coordinated and may overlap. If another outage starts while the power is already off, it does not have any further effect. For example, if three outages are planned: from the $1$st to $10$th second, from the $5$th to $20$th, and from the $15$th to $30$th, the power will go off at the start of the $1$st second, at the $5$th nothing happens (since power is already off), turned on at the $11$th second, turned off again at the $15$th, and turned on at the $31$st. No two teams interrupt the power at the same moment. Time is measured from the $0$ second; in total, there are M+1 seconds (0, 1, …, M).