Tukang Makan

Tukang Makan

Batas Waktu 	0.1s
Batas Memori 	32MB
Deskripsi

Sudahkah anda mengenal Vaislan? Dia adalah tukang makan! Vaislan membayar temannya, The Kid untuk membelikannya makanan.

Vaislan tinggal di planet Dzkysq. Dalam satu hari di Dzkysq, terdapat N menit (1 ≤ N ≤ 20,000) dari menit [1..N]. Karena Vaislan trauma saat memasak air dia membuat gosong air tersebut, Vaislan berencana untuk membeli makanan saja. Terdapat M (1 ≤ M ≤ 50,000) tukang jual makanan dinomori [1..M]. Tiap makanan memiliki Si,Ei, dan Vi. 1 ≤ Si < Ei ≤ N. 1 ≤ Vi ≤ 1,000,000,000. Di planet Dzkysq, tiap tukang jual makanan hanya muncul pada menit "Si" saja dan akan hilang seketika jika pada menit "Si" Vaislan tidak datang. Jika Vaislan mengambil makanan tersebut, maka makanan tersebut harus langsung dimakan dan ia akan mendapat tingkat kepuasan sebanyak Vi dan memenuhi kapasitas perutnya maksimal sebanyak Vi juga. Makanan tersebut akan memenuhi sebagian perut Vaislan sampai habis dicerna pada menit ke-Ei dan langsung hilang dari perut setelah habis dicerna.

Kapasitas perut Vaislan hanyalah P (1 ≤ P ≤ 100). Vaislan tidak dapat makan jika makanan yang dimakan melebihi kapasitas perut Vaislan. Namun, Vaislan dapat memakan sebagian dari suatu makanan yang dipilihnya. Bantulah The Kid untuk memuaskan perut si Vaislan. Tentukan total maksimal tingkat kepuasan perut Vaislan.

Beberapa catatan penting lainnya:

    Dalam satu waktu vaislan bisa ngambil lebih dari satu menu asal masih ada kapasitas perut.
    Mengambil sebagian berarti mengambil X dari Y dimana 1<= X <= Y, dan X bilangan bulat. Waktu untuk mencerna X adalah sama dengan waktu untuk mencerna Y.

Format Masukan
Baris 1 adalah 3 buah bilangan M,N,P. M baris berikutnya berisi 3 buah bilangan Si, Ei, dan Vi.

Format Keluaran
Total kepuasan Vaislan.

Contoh Masukan

7 10 3
1 10 1
2 4 2
4 5 1
4 7 2
4 9 3
5 6 1
6 9 1

3 10 1
1 3 10
3 6 10
6 9 10


Contoh Keluaran

7

3

Penjelasan

Pada contoh pertama Misalkan menu makan Vaislan sebagai berikut.
No 	Nama Makanan 	Waktu Santap 	Waktu Selesai di Cerna 	Kepuasan
1 	Beling 		1 		10 			1
2 	Obor 		2 		4 		2
3 	Badak Bakar 	4 		5 		1
4 	Nasi Goreng 	4 		7 		2
5 	Kupat Tahu 	4 		9 		3
6 	Indomi 		5 		6 		1
7 	Pizza 		6 		9 		1

Dia akan makan Obor, Badak Bakar, Nasi Goreng, Indomi, dan Pizza.

Pada contoh kedua, Vaislan hanya memakan 1/10 bagian dari masing-masing makanan.
Subtask

Subtask #1 (5 point)

    Untuk nilai M diganti menjadi 1 ≤ M ≤ 10.
    1 ≤ V ≤ 1,000,000,000

Subtask #2 (20 point)

    semua nilai V = 1

Subtask #3 (75 point)

    Tidak ada batasan khusus