Решение задач «Ограничение времени: 1 с Ограничение реального времени»,
Информатика в Нижнем Новгороде

Ограничение времени: 1 с Ограничение реального времени: 5 с Ограничение памяти: 1G Недавно Центр Помощи Мигрантам получил в свое распоряжение новое общежитие, которое представляет собой большой коридор, в котором последовательно расположены m комнат. Так как общежитие является достаточно большим, администрация Центра Помощи Мигрантам решила, что в каждой комнате будет проживать не более одного мигранта. Для удобства пронумеруем все комнаты общежития целыми числами от 1 до m . Назовем комнаты i и j соседними, если | i ? j | = 1 . Уже давно в очереди на получение общежития находится n мигрантов. По счастливому стечению обстоятельств n ? m , то есть в новом общежитии хватит мест, чтобы разместить всех мигрантов, находящихся в очереди. По результатам опроса для каждого мигранта были вычислены два параметра: a i и b i . Параметр a i характеризует уровень счастья i -го мигранта при условии, что хотя бы в одной из соседних с ним комнат будет проживать другой мигрант. Параметр b i характеризует уровень счастья i -го мигранта при условии, что во всех соседних с ним комнатах не будут проживать другие мигранты. Администрация Центра Помощи Мигрантам поставила для себя задачу — расселить всех мигрантов таким образом, чтобы максимизировать суммарный уровень их счастья от проживания в общежитии. Помогите этого достичь и вычислите максимально возможный суммарный уровень счастья мигрантов. Формат входных данных Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число t ( 1 ? t ? 100 000 ) — количество наборов входных данных. Далее следует описание наборов входных данных. Первая строка описания набора входных данных содержит два целых числа n и m ( 1 ? n ? 500 000 , 1 ? m ? 10 9 , n ? m ) — количество мигрантов в очереди, а также количество комнат в общежитии. Каждая из следующих n строк описания набора входных данных содержит два целых числа a i и b i ( 1 ? a i , b i ? 10 9 ) — уровень счастья i -го мигранта при условии наличия соседей и при условии отсутствия соседей, соответственно. Гарантируется, что сумма n по всем наборам входных данных не превосходит 10 6 . Формат выходных данных Для каждого набора входных данных выведите одно целое число — максимально возможный суммарный уровень счастья всех мигрантов. Примеры Входные данные 3 1 100 100 50 2 100 10 20 30 10 4 5 1 10 10 1 10 1 10 1 Выходные данные 50 40 40 Примечания В первом примере в очереди находится всего один мигрант. Поэтому при любом расселении у него не будет соседей, а значит уровень его счастья будет равен 50 . Во втором примере в очереди находятся два мигранта. Если их поселить в соседние комнаты, суммарный уровень их счастья будет равен 10 + 30 = 40 . Если их поселить не в соседние комнаты, суммарный уровень их счастья будет равен 20 + 10 = 30 . В третьем примере можно, например, поселить первого мигранта в комнату 1 , а остальных трех мигрантов — в комнаты 3 , 4 и 5 .