Time Shift

Flatland has $n$ cities. Flatland is not on Earth, so a day there lasts $2s$ hours and a year has $T$ days, that is exactly $2sT$ hours.

Each city in Flatland has its own government, and every city has its own laws about shifting clocks. In some cities, for example, there are not only summer and winter time but also spring, autumn, mid-season, holiday, and weekend time. Since the laws differ from city to city, the time in different cities often differs greatly. Naturally, having many different times inconveniences the country's residents.

The city numbered $n$ is the capital of Flatland. To make communication with other countries convenient, the time there is never shifted. It is also known that the difference between the time of any other city and the time of the capital never exceeds $s$ hours in absolute value.

Let us describe how time is measured and how clocks are shifted. In the center of each city stands a huge clock. This clock shows the number of the current day in that city and the current hour. Minutes and seconds are not shown, since the government considers them unimportant. At the start of the year, by an old tradition, the time in all cities is synchronized, and the year in every city begins at midnight, that is, all clocks show zero and the first day begins. Each time midnight arrives in a city, a new day begins there, that is, the number of the current day in that city changes. If a shift day arrives in a city, then at the first noon of that day (when the clock shows $s$ hours) the clock is shifted by the amount specified in the law. A shift never changes the number of the current day, but if the shift is $s$ hours forward, then midnight arrives immediately and, accordingly, the next day begins in that city.

The Special Commission for Assessing the Inconvenience of Flatland has developed a numerical measure of the inconvenience that arises. The hourly inconvenience in the country is the sum of the absolute differences of times over all pairs of cities during one hour. Namely, let $t_i = 2sd_i + c_i$, where $d_i$ is the number of the current day in city $i$ and $c_i$ is the current hour in city $i$. Sum the value $|t_i - t_j|$ over all unordered pairs of distinct cities $\{i, j\}$. The resulting sum is the hourly inconvenience in the country. The yearly inconvenience is the sum of the hourly inconveniences over all hours of the year, that is, over the $2sT$ hours from the start of the year.

The schedules of time shifts in the cities during the year are known. Your task is to compute the yearly inconvenience. At the start of the year the times in all cities coincide and the year begins at midnight, that is, the clocks show zero. A time shift in any city happens only at local noon, that is, at $s$ hours. Shifts connected with synchronizing clocks at the start of the year are not listed, since they are a major cultural event and happen all at once with the arrival of the new year.

The first line contains four integers $n$, $m$, $s$, and $T$ ($2 \le n \le 10^4$; $1 \le m \le 10^5$; $1 \le s \le 10^4$; $1 \le T \le 100$). The next $m$ lines describe time shifts. Each description consists of three numbers $d_i$, $k_i$, and $t_i$: the number of the day on which the shift happens, the number of the city in which the shift happens, and the number of hours by which the time is shifted ($1 \le d_i$; $1 \le k_i \le n - 1$; $-s \le t_i \le s$; $t_i \ne 0$). Each shift is by at most 200 hours.

The input data is guaranteed to be valid. Each city has at most one shift per day. Flatlanders number the days of the year starting from one.

Print a single integer: the yearly inconvenience. It is guaranteed that the answer does not exceed $8 \cdot 10^{18}$.