가장 긴 인생

누구나 가능한 한 오래 살고 싶어 한다. 시간이 흐르면 기술도 발전한다. 여러 시점에 사람의 노화를 평소보다 느리게 하는 항노화 알약이 시장에 나온다. 특히 $x$-$y$ 알약은 규칙적으로 복용하면 $x$초 동안 몸을 $y$초만큼만 늙게 한다. 예를 들어 100-87 알약을 규칙적으로 먹으면 그 다음 100초 동안 몸은 87초만큼만 늙는다. 알약은 한 번에 하나만 먹을 수 있고, 아예 먹지 않을 수도 있다. 이 알약을 쓸 때의 유일한 단점은 복용법이 바뀌기 때문에 알약을 다른 것으로 바꾸면 자동으로 $c$초만큼 늙는다는 점이다. $c$의 값은 모든 알약에 같다. 알약을 전혀 먹지 않던 상태에서 알약을 먹기 시작할 때도 $c$초만큼 늙는다.

$x$-$y$ 알약으로 바꿀 때는 그 알약을 원하는 시간만큼 먹을 수 있다. 다만 알약으로 바꿀 수 있는 시점은 그 알약이 시장에 처음 나온 시각 이후다. 인생은 $t = 0$초에 시작하며, 알약을 쓰지 않으면 $n$초까지 살 수 있다.

각 알약이 시장에 나오는 시각 $t_i$(초)와 $x_i$, $y_i$ 값, 그리고 $c$가 주어진다. 가능한 모든 알약 복용 일정 중에서 가장 오래 살 수 있는 시간을 구하라.

첫 줄에 세 양의 정수 $n$($n \le 3 \cdot 10^9$), $p$($p \le 10^5$), $c$($c \le 10^5$)가 주어진다. $n$은 알약을 먹지 않았을 때 살 수 있는 초 수, $p$는 시장에 나오는 알약의 수, $c$는 다른 알약으로 바꿀 때 자동으로 늙는 초 수다. 이어지는 $p$개의 줄에는 각각 공백으로 구분된 정수 $t_i$, $x_i$, $y_i$가 주어진다($1 \le t_i \le 10^{12}$, $1 \le y_i < x_i \le 10^4$). $i$번째 알약이 나오는 시각과 $x$, $y$ 값이다. 모든 $1 \le i \le n-1$에 대해 $t_{i+1} - t_i > c$가 보장된다.

알약을 적절히 복용했을 때 살 수 있는 최대 초 수를 실수 하나로 출력하라. 답은 상대 오차 또는 절대 오차 $10^{-6}$ 이내로 정확해야 한다.