22165번 - Перевод времени 다국어

문제

В стране Флатландии n городов. Флатландия находится не на Земле, а потому сутки во Флатландии длятся 2s часов, а в году T суток, то есть ровно 2sT часов.

Каждый город Флатландии имеет свое правительство, и так случилось, что в каждом городе приняты свои законы о переводе часов. В некоторых городах, к примеру, время бывает не только летнее и зимнее, но и весеннее, осеннее, демисезонное, праздничное и выходное. Так как законы в каждом городе свои, то часто случается ситуация, когда время в разных городах сильно отличается. Естественно, наличие большого числа различных времен вызывает неудобство у жителей страны.

Город, имеющий номер n, является столицей Флатландии. В нем, ради удобства общения с другими странами, время не переводят никогда. Также известно, что разница между временем любого другого города и временем столицы никогда не превышает s часов по абсолютной величине.

Опишем, как происходит процесс измерения времени и перевода часов. В центре каждого города стоит огромные часы. Эти часы показывают номер текущего дня в этом городе, а также текущий час. Минуты и секунды на часах не показываются, так как правительство считает их неважными. В начале года, по старой традиции, время во всех городах синхронизируется, и год в каждом городе начинается в полночь, то есть все часы показывают ноль и начинается первый день. При каждом наступлении полуночи в городе начинается новый день, то есть меняется номер текущего дня в этом городе. Если в городе наступает день перевода, то при первом наступлении полудня (часы показывают s часов) этого дня происходит перевод часов на указанную в законе величину. Перевод никогда не меняет номер текущего дня, однако если перевод производится на s часов вперед, то сразу же наступает полночь и, соответственно, следующий день в этом городе.

Специальная Комиссия по Оценке Неудобства Флатландии разработала численную характеристику, позволяющую оценить возникающее неудобство. Часовым неудобством в стране называется величина, равная сумме модулей разниц времен для всех пар городов в течении некоторого часа. А именно, обозначим как t_i величину, равную 2sd_i + c_i, где d_i — номер текущего дня в i-ом городе, а c_i — номер часа в i-ом городе. Просуммируем величину |t_i – t_j| для всех неупорядоченных пар различных городов {i, j}. Полученная сумма и есть часовое неудобство в стране. Неудобством за год является сумма часовых неудобств по всем часам в году, то есть по 2sT часам с начала года.

Известны графики перевода времен в городах в течение года. Ваша задача состоит в том, чтобы посчитать неудобство за год. В начале года времена по всех городах совпадают и год начинается с полуночи, то есть на часах ноль. Перевод времени в любом городе происходит только в полдень по местному времени, то есть в s часов. Переводы, связанные с синхронизацией часов в начале года не указаны, так как они являются крупным культурным событием и происходят все одновременно с наступлением нового года.

입력

Первая строка содержит четыре целых числа n, m, s и T (2 ≤ n ≤ 10⁴; 1 ≤ m ≤ 10⁵; 1 ≤ s ≤ 10⁴; 1 ≤ T ≤ 100). Далее следуют m строк, описывающих переводы времени. Каждое описание состоит из трех чисел d_i, k_i и t_i — номер дня, в который происходит перевод времени, номер города, в котором происходит перевод, и число часов, на которые переводится время (1 ≤ d_i; 1 ≤ k_i ≤ n – 1; –s ≤ t_i ≤ s; t_i ≠ 0). Каждый перевод совершается не более, чем на 200 часов.

Гарантируется, что данные во входном файле корректны. В каждом городе происходит не более одного перевода в день. Дни в году Флатландцы нумеруют c единицы.

출력

Выведите единственное целое число — неудобство за год. Гарантируется, что ответ не превысит 8·10¹⁸.

제한

힌트