Гоша выходит на охоту. Его цель — поймать как можно больше покемонов. У Гоши есть a покеболов и b ультраболов. Всего покемонов n. Они пронумерованы числами от 1 до n. Про i-го покемона Гоша знает, что если бросить в него покеболом, то с вероятностью pi данный покемон будет пойман. Если бросить в i-го покемона ультраболом, то он будет пойман с вероятностью ui. В каждого покемона можно бросить не более чем одним болом каждого типа.
Охота происходит следующим образом: Гоша сначала выбирает не более чем a покемонов, в которых он будет бросать покеболами, и не более чем b покемонов, в которых он будет бросать ультраболами. После этого Гоша бросает в выбранных покемонов выбранными болами. Если он бросает в покемона и покеболом, и ультраболом, то данный покемон будет пойман, если он будет пойман хотя бы одним из двух болов. Результаты бросков независимы.
Гоша хочет узнать, чему равно математическое ожидание количества пойманных покемонов, если он будет действовать оптимально. Иными словами, он хочет узнать максимально возможное математическое ожидание.
Выходные данные
Выведите максимально возможное математическое ожидание количества пойманных покемонов. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает 10 - 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 2
1.000 0.000 0.500
0.000 1.000 0.500
|
2.75
|
|
2
|
4 1 3
0.100 0.500 0.500 0.600
0.100 0.500 0.900 0.400
|
2.16
|
|
3
|
3 2 0
0.412 0.198 0.599
0.612 0.987 0.443
|
1.011
|