C. Помощь нуждающимся
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Малек — богатый человек. К тому же он очень щедрый. Поэтому он решил разделить свои деньги между бедняками. Благотворительному фонду известно 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.

Эффект благотворительности — это максимальное значение суммы денег, имеющейся у бедняка после того, как Малек закончит раздавать свои деньги. Для каждой рекомендации фонд знает вероятность того, что Малек её примет. Фонд хочет знать математическое ожидание эффекта благотворительного акта Малека. Они попросили Вас помочь им в нахождении этой величины.

Вам дан список рекомендаций, для каждой рекомендации также дана вероятность того, что Малек примет её. Вам дано количество денег, изначально имеющееся у каждого человека. Требуется найти математическое ожидание эффекта благотворительности.

Входные данные

В первой строке даны два целых числа через пробел — n, q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5000).

Во второй строке содержатся n разделённых пробелами целых чисел a1, a2, ..., an (0 ≤ ai ≤ 109), обозначающие, что у человека i изначально есть ai долларов.

В каждой из следующих q строк записано по три целых числа через пробел li, ri, pi (1 ≤ li ≤ ri ≤ n, 0 ≤ p ≤ 1), где li и ri — два числа, описывающих отрезок рекомендации, а pi — вещественное число, данное ровно с тремя знаками после десятичной точки, равное вероятности того, что Малек примет данную рекомендацию.

Обратите внимание, что один и тот же отрезок может появляться в рекомендациях несколько раз.

Выходные данные

Выведите математическое ожидание. Ответ будет засчитан, если его абсолютная или относительная погрешность будет составлять не более 10 - 6.

Примеры
Входные данные
5 2
1 7 2 4 3
1 3 0.500
2 2 0.500
Выходные данные
8.000000000
Входные данные
5 2
281 280 279 278 282
1 4 1.000
1 4 0.000
Выходные данные
282.000000000
Входные данные
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