Kompetisi Sains Nasional (KSNP) Provinsi 2021 - Komputer, Nomor 19–22

Apabila semua vitamin berdosis tinggi dan Pak Dengklek mempunyai uang sebanyak 7, berapa total kandungan vitamin maksimal yang bisa diperoleh?

Apabila semua vitamin berdosis rendah dan Pak Dengklek mempunyai uang sebanyak 8, berapa total kandungan vitamin maksimal yang bisa diperoleh?

Apabila vitamin A dan B berdosis rendah sementara vitamin C, D, dan E berdosis tinggi dan Pak Dengklek mempunyai uang sebanyak 15, berapa total kandungan vitamin maksimal yang bisa diperoleh?

MEMBUAT PROGRAM

Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan total kandungan vitamin maksimal yang diperoleh Pak Dengklek dengan ketentuan sebagai berikut:

Format Masukan:
Baris pertama berisi dua buah bilangan N dan M yang menyatakan banyaknya vitamin dan uang yang dimiliki Pak Dengklek. N baris berikutnya berisi 3 buah bilangan H_i K_i D_i yang menyatakan harga, kandungan, dan dosis dari vitamin ke-i. Apabila D_i = 1, maka vitamin ke-i berdosis tinggi. Apabila D_i = 0, maka vitamin ke-i berdosis rendah.

Format Keluaran:
Sebuah baris yang berisi sebuah bilangan V yang menyatakan total kandungan vitamin maksimal yang dapat dicapai.

Contoh Masukan dan Keluaran:

2 10
1 2 1
2 1 0

6

3 10
1 5 1
1 10 1
1 15 1

30

Penjelasan Contoh:
Pada contoh pertama, tentu lebih untung membeli vitamin 1. Namun, vitamin pertama berdosis tinggi sehingga tidak dapat mengonsumsi lebih dari satu. Oleh karena itu, sisa uangnya digunakan untuk membeli vitamin 2.

Batasan:

Untuk kasus uji pada subtask 1, berlaku (Point 50%):

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10000
• 1 ≤= H[i] ≤= M, 1 ≤= K[i] ≤= 10⁵
• D_i = 1

Untuk kasus uji pada subtask 2, berlaku (Point 50%):

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10000
• 1 ≤= H[i] ≤= M, 1 ≤= K[i] ≤= 10⁵
• D[i] = 0 atau D[i] = 1