愛麗絲要開車去上班，上班的路上有許多紅綠燈，這讓愛麗絲很難過。為了上班不遲到，她給自己的車安裝了氮氣噴射裝置?，F(xiàn)在她想知道自己上班最短需要多少時間。 

愛麗絲的車最高速度是米每秒，并且經(jīng)過改裝后，可以瞬間加速到小于等于最高速的任意速度，也可以瞬間停止。 

愛麗絲家離公司有 N 米遠，路上有 M 個紅綠燈，第 i 個紅綠燈位于離愛麗絲家 A_i 米遠的位置，綠燈持續(xù) B_i 秒，紅燈持續(xù) C_i 秒。在初始時（愛麗絲開始計時的瞬間），所有紅綠燈都恰好從紅燈變?yōu)榫G燈。如果愛麗絲在綠燈變紅的瞬間到達紅綠燈，她會停下車等紅燈，因為她是遵紀守法的好市民。 

氮氣噴射裝置可以讓愛麗絲的車瞬間加速到超光速（且不受相對論效應的影響?。?，達到瞬移的效果，但是愛麗絲是遵紀守法的好市民，在每個紅綠燈前她都會停下氮氣噴射，即使是綠燈，因為紅綠燈處有斑馬線，而使用氮氣噴射裝置通過斑馬線是違法的。此外，氮氣噴射裝置不能連續(xù)啟動，需要一定時間的冷卻，表現(xiàn)為通過 K 個紅綠燈后才能再次使用。（也就是說，如果 K = 1，就能一直使用啦?。┏跏紩r，氮氣噴射裝置處于可用狀態(tài)。 

第一行四個正整數(shù) N、M、K、V，含義如題面所述。

接下來 M 行，每行三個正整數(shù) A_i、B_i、C_i，含義如題面所述。 

90 2 2 2
30 20 20
60 20 20

80

愛麗絲在最開始直接使用氮氣噴射裝置瞬間到達第一個紅綠燈，然后綠燈通過，以最高速行進 60 秒后到達第二個紅綠燈，此時綠燈剛好變紅，于是她等待 20 秒再次變?yōu)榫G燈后通過該紅綠燈，此時氮氣噴射裝置冷卻完畢，愛麗絲再次使用瞬間到達公司，總共用時 80 秒。

對于 30% 的數(shù)據(jù)，N ≤ 100; M ≤ 10; M < K; V = 1.

對于 60% 的數(shù)據(jù)，N ≤ 1000; M ≤ 100; K ≤ 50; B_i ,C_i ≤ 100; V ≤ 10.

對于 100% 的數(shù)據(jù)，0 < N ≤ 10⁸ ; M ≤ 1000; K ≤ 1000; 0 < B_i ,C_i ≤ 10⁶ ; 0 < V ≤ 10⁶ ; 0 < A_i < N; 對任意 i < j, 有 A_i < A_j .