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