| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Кевин решил как следует отдохнуть. Для начала он хочет послушать музыку на своем плеере.
На его плеере сохранено $n$ песен. Известен порядок, в котором будут воспроизводиться композиции.
В некоторых песнях есть особенно классные отрезки, которые нравятся Кевину. Для каждого из них известно, сколько радости приносит прослушивание одной секунды этого отрезка. Оставшиеся моменты песни, которые не вошли ни в один классный отрезок, не приносят радости.
Радость Кевина выражается целым неотрицательным числом. Перед началом прослушивания она равна 0ドル$. Кевин хочет, чтобы его радость достигла $F$.
Также в плеере доступна возможность ускорить воспроизведение. При ускорении за одну секунду реального времени проходит $v$ секунд песни. Если во время ускорения песня заканчивается, то ускорение продолжается с начала следующей. Если во время ускорения встречается некоторая часть классного отрезка, то радости она не приносит.
Если количество радости, доставляемое от прослушивания некоторого отрезка равно $f,ドル и Кевин прослушивал его в течении $t$ секунд ($t \ge 0,ドル $t$ вещественно), то Кевин получит $f \cdot{} t$ радости.
Ускорять воспроизведение также можно в течении любого вещественного количества секунд.
Ускорение можно начать и закончить в любой момент времени. Включение и выключение ускорения происходят мгновенно.
Плейлист не зациклен, то есть после того как все песни из плейлиста воспроизведены, плеер заканчивает свою работу.
Как только радость Кевина достигает $F,ドル он сразу же прекращает слушать музыку. Помогите ему определить, какое наименьшее время придется провести с плеером, чтобы достичь радости $F$.
В первой строке находятся три натуральных числа $n,ドル $v,ドル $F$ (1ドル \le n \le 10^5,ドル 1ドル \le v, F \le 10^9$) --- количество песен, коэффициент ускорения и радость, которой хочет достигнуть Кевин.
В следующих $n$ строках идет описание классных отрезков в песне: в $i$-й из них содержатся два целых числа $t_i,ドル $k_i$ (1ドル \le t_i \le 10^9, 0 \le k_i$) --- длина $i$-й песни, количество классных отрезков в ней, а затем $k_i$ троек чисел $l_{i,j},ドル $r_{i,j},ドル $f_{i,j}$ (0ドル \le l_{i,j} \le r_{i,j} \le t_i$ , $r_{i,j} \le l_{i,j+1}$ , 1ドル \le f_{i,j} \le 10^9$) --- с какой секунды по какую находится классный отрезок и количество радости, которое доставляет прослушивание одной секунды этого отрезка. Все $l_{ij},ドル $r_{ij},ドル $f_{ij}$ целые.
Песни заданы в порядке воспроизведения.
Сумма всех $k_i$ не превосходит 10ドル^5$.
Выведите единственное вещественное число --- количество секунд, которое нужно провести с плеером, чтобы достичь радости $F$. Если сделать этого невозможно, выведите $-1$.
Ответ будет считаться правильным, если относительная или абсолютная погрешность не будет превосходить 10ドル^{-8}$.
3 2 5 4 2 0 1 1 2 4 1 6 2 0 1 1 1 5 4 3 1 1 3 2
3.7500000000
2 2 10 3 2 0 1 1 1 3 1 2 1 0 2 3
-1
4 1 8 5 1 2 4 2 4 1 1 3 1 3 1 0 1 3 6 2 0 2 10 3 5 9
9.6666666667