시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.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}$.

예제 입력 1

3 2 5
4 2 0 1 1 2 4 1
6 2 0 1 1 1 5 4
3 1 1 3 2

예제 출력 1

3.7500000000

예제 입력 2

2 2 10
3 2 0 1 1 1 3 1
2 1 0 2 3

예제 출력 2

-1

예제 입력 3

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

예제 출력 3

9.6666666667