C. Хөгжилтэйгээр салютыг үзэцгээе

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Энэ жилийн наадам хотын төв гудамжинд явагдах аж. Төв гудамж $n$ хэсэгтэй бөгөөд хэсгүүдийг $1$-с эхэлж $n$ хүртэл зүүнээс дугаарладаг. Зэрэгцээ хэсэг болгон хоорондоо $1$ зайтай.

Наадмын үеэр $m$ салют буудна. $i$-р ($1 ≤ i ≤ m$) салтютийг $a_i$-р хэсгээс $t_i$ хугацаанд харвана. Хэрвээ та $i$-р салютийг буудах үед $x$ ($1 ≤ x ≤ n$) хэсэгт байх юм бол $b_i-|a_i-x|$ аз жаргал авна. (аз жаргал сөрөг байж болохыг анхаар)

Та нэгж хугацаанд хамгийн ихдээ $d$ зайг туулж чаддаг ба төв гудамжнаас гарч явахыг хориглосон. Мөн хугацааны 1-р агшинд аль ч хэсэгт байж чадах ба галт наадмаас хамгийн их аз жаргалыг авахыг хүсч байгаа. Уг хамгийн их аз жаргалын хэмжээг ол.

2 салют зэрэг харваж болохыг анхаараарай.

Оролт

Эхний мөрөнд $n$, $m$, $d$ ($1 ≤ n≤ 150000$, $1 ≤ m ≤ 300$, $1 ≤ d ≤ n$) өгөгдөнө.

Дараагийн $m$ мөр бүрт $i$-р салютын мэдээлэл $a_i$, $b_i$, $t_i$ ($1 ≤ a_i ≤ n$, $1 ≤ b_i ≤ 10^9$, $1 ≤ t_i ≤ 10^9$) байна.

$t_i ≤ t_{i+1}$ ($1 ≤ i < m$) нөхцөл үргэлж биелэнэ.

Гаралт

Бүх салютыг үзэх үед авч чадах хамгийн их аз жаргал болох бүхэл тоог хэвлэнэ.

Жич: C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
50 3 1
49 1 1
26 1 4
6 1 10
Гаралт
-31
Оролт
10 2 1
1 1000 4
9 1000 4
Гаралт
1992
Сэтгэгдлүүдийг ачааллаж байна...