Автобус
Василь працює водієм автобуса, і його робота дійсно непроста: він перевозить пасажирів з пункту A до пункту B. Під час роботи він повинен дотримуватися безпеки та намагатися завершити маршрут якнайшвидше. Крім того, кожен водій зобов'язаний дотримуватися правил дорожнього руху, інакше його можуть оштрафувати місцеві правоохоронці.
Маршрут Василя складається з N (1 ≤ N ≤ 1000) відрізків, які він проїжджає послідовно, починаючи з першого і завершуючи останнім, N-м відрізком. Для кожного відрізка задана його довжина в кілометрах D_{i} (1 ≤ D_{i} ≤ 1000).
На маршруті Василя діють обмеження швидкості. Кожен відрізок має своє обмеження швидкості L_i км/год (1 ≤ L_i ≤ 100000). Якщо Василь перевищить швидкість на i-му відрізку, його автобус буде негайно зупинений поліцейським, який витратить H_i (1 ≤ H_i ≤ 1000) годин на оформлення документів. Водій може бути зупинений лише один раз на кожному відрізку.
Автобус рухається по маршруту з постійною швидкістю S, яку Василь обирає на початку маршруту (в пункті A). Автобус не може перевищувати максимальну конструктивну швидкість, яка дорівнює M км/год (1 ≤ M ≤ 100000).
Допоможіть Василю вибрати правильну швидкість, щоб дістатися до пункту B якомога швидше.
Вхідні дані
Перший рядок вхідних даних містить кількість тестових випадків T. Далі йде опис T тестових випадків, T ≤ 100.
Кожен тестовий випадок починається з окремого рядка, що містить 2 числа, розділені пробілом: кількість відрізків N на маршруті Василя та максимальна допустима швидкість автобуса M. Кожен з наступних i-х рядків містить опис кожного з N відрізків, зокрема значення D_i, L_i і H_i, розділені пробілами, для відповідного i-го відрізка.
Вихідні дані
Для кожного тестового випадку виведіть оптимальну швидкість автобуса. У разі неоднозначності вибору слід обрати найбільше значення.