Traveling Witch Problem

빗자루를 다루는 이는 한 명의 아름다운 소녀, 검은 로브와 삼각 모자를 몸에 걸쳤고, 잿빛 머리카락은 바람에 흩날렸습니다.

그곳에 다른 누군가가 있었다면 분명 모두 돌아보며 한숨을 흘리고 말 정도의 미모를 겸비한 그녀는 대체 누구일까요?

그렇습니다. 바로 저입니다.

— 일레이나, 「마녀의 여행」

유명한 빵가게가 많은 나라가 근처에 있다는 소문을 듣게 된 저는, 재빨리 빗자루를 타고 그곳에 도착했습니다. 이 나라는 $1$번 마을부터 $N$번 마을까지 총 $N$개의 마을로 이루어져 있고, $1$번 빵가게부터 $M$번 빵가게까지 총 $M$개의 빵가게가 존재합니다. 신기하게도, 이 나라의 빵가게들은 아래와 같은 특징이 있습니다.

• $i$ $(1 \le i \le M)$번 빵가게는 $v_i$번 마을에 위치해 있습니다.
• $i$번 빵가게의 빵의 가격은 동화 $A_i$개입니다.
• 이 나라의 빵가게 주인들은 하나같이 특이한데, $i$번 빵가게에서는 적어도 $B_i$만큼의 마력이 있는 마녀에게만 빵을 판매한다고 합니다.

제 초기 마력은 $0$이고, 마력을 원하는 만큼 올릴 수 있지만 $1$만큼 올릴 때마다 동화 $K$개를 대가로 지불해야 합니다. 돈 계산은 머리 아픈 일입니다. 저 대신 모든 마을에서 빵을 적어도 한 번씩 구매하기 위해 필요한 동화 개수의 최솟값을 구해 주세요.

첫째 줄에 마을의 수 $N$, 빵가게의 수 $M$, 일레이나의 마력을 $1$만큼 올리기 위해 필요한 동화의 수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le M \le 200\,000;$ $1 \le K \le 10^9)$

두 번째 줄부터 $M$줄에 걸쳐 $i$번째 빵집이 위치한 마을의 번호 $v_i$, 빵의 가격 $A_i$, 필요한 마력 $B_i$가 공백으로 구분되어 주어진다. $(1 \le v_i \le N;$ $0 ≤ A_i, B_i ≤ 10^9)$

주어지는 입력은 모두 정수이고, 항상 모든 마을에서 빵을 구입할 수 있는 입력만 주어진다.

첫째 줄에 일레이나가 모든 마을에서 빵을 적어도 한 번씩 구매하기 위해 필요한 동화 개수의 최솟값을 출력한다.