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