Question 16 — Tebas Tebang Bambu 3

Di belakang rumah Pak Dengklek terdapat N bilah bambu. Bambu ke-i memiliki panjang sebesar A_{i} satuan. Pak Dengklek berencana untuk menjual seluruh bambunya. Saat Pak Dengklek ingin berjualan di pasar, diketahui bahwa pelanggan tidak mau membeli bambu secara eceran. Pelanggan hanya mau membeli bambu dalam satuan ikat yang memenuhi dua syarat berikut:

• Setiap ikat bambu harus terdiri dari setidaknya M bilah bambu.
• Setiap bambu dalam satu ikat yang sama harus memiliki panjang yang sama.

Boleh jadi dua atau lebih ikat bambu yang berbeda memiliki panjang bambu yang sama.

Pak Dengklek ingin mengelompokkan seluruh bambunya ke dalam satu atau lebih ikat. Agar memenuhi kedua syarat di atas, Pak Dengklek dapat memangkas setiap bambunya sehingga panjangnya berkurang. Untuk mempertahankan kekokohan bambu, Pak Dengklek dapat memangkas setiap bambu agar panjangnya berkurang maksimal sepanjang K satuan.

Perhatikan bahwa bagian bambu yang terpangkas tidak dapat digunakan kembali. Perhatikan juga bahwa setiap bambu hanya boleh dipangkas, dan tidak boleh dibelah menjadi lebih dari satu bilah.

Apabila Pak Dengklek harus menjual seluruh bambunya, berapakah banyak ikat maksimum yang dapat ia jual? Perlu diperhatikan bahwa bisa jadi Pak Dengklek tidak dapat menjual seluruh bambunya.

Pak Dengklek akan menjual 18 bilah bambu dengan panjang sebagai berikut:

[1, 1, 3, 3, 4, 5, 6, 7, 8, 9, 9, 13, 13, 14, 14, 14, 15, 16]

Apabila Pak Dengklek dapat memangkas bambu-bambunya agar panjangnya berkurang paling banyak 2 satuan, maka berapakah banyaknya ikat bambu maksimum yang dapat Pak Dengklek jual jika setiap ikat bambu harus terdiri dari setidaknya 3 bilah bambu dan Pak Dengklek harus menjual seluruh bambunya?

Jika ternyata Pak Dengklek tidak mungkin menjual seluruh bambunya, jawablah dengan -1.

Jawab: …………………………… {tuliskan jawaban dalam bentuk angka saja}