Сегодня большой день для любителей онлайн-игр — всё мировое сообщество следит за финальными матчами чемпионата по знаменитой многопользовательской игре. У Макса, разумеется, всё не как у людей — в этот знаменательный день он умудрился оказаться в поезде, да ещё и с почти разряженным ноутбуком!
Разумеется, Макс заранее знал о чемпионате и составил список из N матчей, которые он хотел бы посмотреть. Матчи чемпионата транслируются в Интернете: i-й матч начинается в момент времени Li и заканчивается в момент времени Ri. Несколько матчей могут транслироваться одновременно.
К сожалению, ноутбук Макса вот-вот разрядится: заряда аккумулятора хватит на непрерывную работу в течение M единиц времени. Макс пока выключил свой ноутбук: он решил, что включит его в определённый момент времени и будет смотреть матчи, не отключая ноутбук, до тех пор, пока он не разрядится.
Подскажите Максу, когда именно включить ноутбук, чтобы он сумел посмотреть как можно больше матчей целиком. При необходимости Макс может смотреть несколько трансляций одновременно — на скорость разрядки ноутбука это не влияет.