Малек — богатый человек. К тому же он очень щедрый. Поэтому он решил разделить свои деньги между бедняками. Благотворительному фонду известно n бедняков, занумерованных числами от 1 до n. Фонд дал Малеку q рекомендаций. Рекомендация — это отрезок [l, r], обозначающий, что фонд рекомендовал Малеку дать по доллару каждому человеку, чей номер есть в этом отрезке.
У фонда необычные правила касательно рекомендаций. Согласно этим правилам, рекомендации даются так, что для любых двух рекомендаций [a, b] и [c, d] выполняется одно из следующих условий:
- Эти два отрезка не пересекаются. Более формально, либо a ≤ b < c ≤ d, либо c ≤ d < a ≤ b
- Один из этих двух отрезков лежит внутри другого. Более формально, либо a ≤ c ≤ d ≤ b, либо c ≤ a ≤ b ≤ d.
Эффект благотворительности — это максимальное значение суммы денег, имеющейся у бедняка после того, как Малек закончит раздавать свои деньги. Для каждой рекомендации фонд знает вероятность того, что Малек её примет. Фонд хочет знать математическое ожидание эффекта благотворительного акта Малека. Они попросили Вас помочь им в нахождении этой величины.
Вам дан список рекомендаций, для каждой рекомендации также дана вероятность того, что Малек примет её. Вам дано количество денег, изначально имеющееся у каждого человека. Требуется найти математическое ожидание эффекта благотворительности.
Выходные данные
Выведите математическое ожидание. Ответ будет засчитан, если его абсолютная или относительная погрешность будет составлять не более 10 - 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 7 2 4 3
1 3 0.500
2 2 0.500
|
8.000000000
|
|
2
|
5 2
281 280 279 278 282
1 4 1.000
1 4 0.000
|
282.000000000
|
|
3
|
3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900
|
4.465000000
|