BNPCHS (Bina Nusantara Programming Contest for High School Students) 2010 - Penyisihan Soal 2

Postingan kali ini adalah lanjutan dari BNPCHS 2010 soal 1 yang telah saya post sebelumnya, baiklah langsung saja ini dia soal ke dua dari  Penyisihan BNPCHS 2010 beserta jawaban saya.

Potong Gaji

Time limit: 3 s

Memory limit: 64 MB

Perusahaan yang dijalankan Pak Jangkung saat ini sedang mengalami kerugian. Beliau memperkerjakan N orang karyawan yang masing-masing memiliki gaji Gi per bulan. Pak Jangkung ingin memangkas pengeluaran perusahaannya dengan membatasi total gaji yang harus beliau bayar per bulan.

Pak Jangkung ingin memangkas total gaji dengan aturan sebagai berikut:

1. Pak Jangkung menentukan gaji tertinggi adalah H.
   • Semua karyawan yang gajinya di atas H per bulan akan dipotong gajinya hingga menjadi H per bulan.
   • Semua karyawan yang gajinya tidak lebih dari H per bulan tidak mengalami perubahan.
2. Total gaji yang harus beliau bayar per bulan tidak melebihi M.

Pak Jangkung harus menyelamatkan perusahaannya, namun beliau juga sayang dengan karyawan-karyawannya, oleh karena itu beliau ingin nilai H sebesar mungkin. Bantu Pak Jangkung untuk menentukan nilai H terbesar yang mungkin. Output -1 jika Pak Jangkung tidak perlu melakukan pemotongan gaji sama sekali.

Input Format

Baris pertama berisi sebuah bilangan bulat T (1 <= T <= 100) yang menyatakan jumlah kasus. Setiap kasus dimulai dengan dua buah bilangan bulat N dan M (1 <= N <= 10.000, 1 <= M <= 1.000.000.000) yang menyatakan banyaknya karyawan dan total gaji maksimal yang diinginkan pak Jangkung. Baris berikutnya berisi N buah bilangan bulat Gi(1 <= Gi  <= 100.000) yang menyatakan gaji setiap karyawan saat ini.

Output Format

Untuk setiap kasus, output dalam satu baris sebuah bilangan bulat yang menyatakan batas gaji tertinggi yang mungkin. Output -1 jika pemotongan gaji tidak diperlukan.

Contoh Input

3
3 1000
500 600 199
4 10000
2500 3000 2500 1000
4 10000
90000 5000 100 3500

Contoh Output

400
-1
3300

Nah ini dia jawaban saya, saya menggunakan bahasa pemrograman C++ kali ini.

Kode Sumber:

Saat menjalankan file executable-nya:

Input

Output

Yoosh, itu dulu dari saya. sampai ketemu di soal ke tiga penyisihan BNPCHS 2010 teman! Keep coding coders! :D