В Королевстве Ланнистеров n замков и несколько стен, соединяющих два замка, никакие два замка не соединены более, чем одной стеной, ни одна стена не соединяет замок с собой.
Сир Джейме Ланнистер узнал, что Дейенерис Таргариен собирается атаковать его королевство. Он хочет защитить свои владения. У него есть k литров странной жидости. Он хочет распределить эту жидкость между замками так, чтобы каждый замок содержал некоторое количество жидкости (возможно, нулевое или нецелое количество литров). После этого стабильность стены, соединяющей замки a и b, содержащие x и y литров жидкости, соответственно, равна x·y.
Ваша задача — найти максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь
Выходные данные
Выведите одно число — максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь.
Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 6.
А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если 
.
Примечание
В первом примере, если замки 1, 2, 3 содержат 0.5, 0.5, 0 литров жидкости, соответственно, ответ равен 0.25.
Во втором примере, если замки 1, 2, 3, 4 содержат 1.0, 1.0, 1.0, 1.0 литров жидкости, ответ равен 4.0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
0 1 0
1 0 0
0 0 0
|
0.250000000000
|
|
2
|
4 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
|
4.000000000000
|