Макс решил, что так как он много путешествует по стране, он мог бы немного скомпенсировать свои расходы, а может, даже подзаработать, если станет курьером — будет брать с собой различные посылки и перевозить их между городами.
Макс может посещать $$$N$$$ различных городов. В некоторых городах можно взять посылку, чтобы отвести её в другой город. Вещи отправляются регулярно, поэтому после доставки посылки можно вновь взять такую же в исходном городе. В каждый момент времени Макс может перевозить только одну посылку.
За доставку посылки из города $$$A$$$ в город $$$B$$$ курьер получает вознаграждение размером $$$P_{AB}$$$ рублей, а время поездки из города $$$A$$$ в город $$$B$$$ равно $$$T_{AB}$$$.
Макс хочет составить такой кольцевой маршрут $$$X_1, X_2, ..., X_K$$$, чтобы, взяв посылку в городе $$$X_1$$$, доставить её в город $$$X_2$$$, там взять следующую посылку и доставить её в город $$$X_3$$$, и так далее, а в конце взять посылку в городе $$$X_K$$$ и доставить её в город $$$X_1$$$, после чего повторять всё путешествие заново. Из всех кольцевых маршрутов Максу интересен наиболее выгодный, то есть такой, у которого отношение суммарного вознаграждения к общему времени пути ($$$L=\frac{\sum{P}}{\sum{T}}$$$) максимально.
Помогите Максу отыскать нужный маршрут.
Выходные данные
Если необходимого маршрута не существует, выведите $$$-1$$$.
Иначе в первой строке выведите одно вещественное число с точностью не менее 6 знаков после запятой — максимально возможное значение $$$L$$$.
Во второй строке выведите одно целое число $$$K$$$ — количество городов в маршруте.
В третьей строке выведите $$$(K + 1)$$$ целое число — номера городов маршрута в порядке обхода. Первое и последнее числа должны совпадать, остальные числа должны быть различны. Если вариантов ответа несколько, выведите любой.