Автобус
Василий работает водителем автобуса, и у него есть по-настоящему тяжелая работа: он перевозит пассажиров из пункта A в пункт B. При этом он должен выполнять свою работу безопасно и как можно быстрее. Кроме того, каждый водитель должен повиноваться дорожным правилам и нормам, иначе, он будет оштрафован местной полицией.
Маршрут Василия состоит из N (1 ≤ N ≤ 1000) отрезков, которые он проезжает последовательно, начиная от 1-го и завершая N-м отрезком. У каждого отрезка задана длина в километрах D_{i }_{(1 ≤ Di ≤ 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-го отрезка.
Выходные данные
Для каждого тестового случая выведите оптимальную скорость автобуса. В случае неоднозначного ответа следует выбрать наибольшее значение.