Ходіння по дошці
Купка піратів успішно захопила комерційне судно. Сам корабель занадто пошкоджений, тому весь вантаж потрібно перевантажити на піратський корабель.
Пірати закріпили дошку між обома кораблями, яку можна використовувати для переходу, але вона витримує лише одного пірата за раз.
Кожен пірат виконує наступну рутину:
Пройти по дошці з піратського корабля на комерційний корабель
Взяти предмет з трюму і повернутися до дошки
Перейти по дошці назад на піратський корабель з предметом
Покласти предмет у трюм і повернутися до дошки
Кожен з цих чотирьох кроків займає певну кількість часу для кожного пірата. Кожен пірат повторюватиме ці кроки, поки кількість піратів на комерційному кораблі не зрівняється з кількістю предметів там (тобто більше нічого не залишиться для пірата, щоб забрати).
Якщо пірат підходить до дошки, і вона зайнята іншим піратом, він чекатиме на своєму боці дошки. Коли дошка звільняється і на обох сторонах дошки є пірати, пірати на стороні комерційного судна (які несуть якийсь предмет) йдуть першими. На обох сторонах дошки пірати стають у чергу, тобто перший, хто туди прийшов, буде першим, хто перейде. Якщо два або більше піратів прибудуть на одну сторону дошки одночасно, пірат, який був найповільнішим (тобто той, хто витратив найбільше часу на дорогу до і з трюму на цьому кораблі), йде першим. Чи можете ви визначити, скільки часу знадобиться, перш ніж останній пірат перейде дошку з останнім предметом?
Вхідні дані
Перша строка вхідних даних містить одне число: кількість тестових випадків, які слідують. Кожен тестовий випадок має наступний формат:
Один рядок з двома цілими числами N та P, що задовольняють 1 ≤ N ≤ 100,000 та 1 ≤ P ≤ 1,000: кількість предметів на комерційному судні та кількість піратів, відповідно.
P рядків, кожен з 4 цілими числами t_1 до t_4, що задовольняють 1 ≤ t_i ≤ 1,000: час у секундах, який потрібен цьому пірату для виконання кожного кроку (як зазначено вище).
На початку всі пірати стоять у черзі на дошці на піратському кораблі в порядку, вказаному у вхідних даних (перший пірат перший переходить).
Вихідні дані
Для кожного тестового випадку у вхідних даних вихід повинен містити одне ціле число в одному рядку: час у секундах між моментом, коли перший пірат починає переходити дошку, і моментом, коли останній пірат перейшов дошку, несучи останній предмет.