- Time limit: 1.00 s
- Memory limit: 512 MB
Tehtaassa on n konetta, joista jokainen valmistaa samaa tuotetta. Tavoitteesi on muodostaa yhteensä t tuotetta.
Tiedät jokaisesta koneesta, montako sekuntia sillä kuluu valmistaa yksi tuote. Koneet voivat toimia samaan aikaan, ja voit vapaasti päättää, milloin käynnistät koneita.
Mikä on pienin aika, jossa pystyt tuottamaan t tuotetta?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja t: koneiden määrä ja tuotteiden määrä.
Seuraavalla rivillä on n kokonaislukua k_1,k_2,\ldots,k_n: kuinka kauan kultakin koneelta kuluu aikaa valmistaa yksi tuote.
Tuloste
Tulosta yksi kokonaisluku: pienin aika, jossa pystyt valmistamaan t tuotetta.
Rajat
- 1 \le n \le 5 \cdot 10^5
- 1 \le t \le 10^9
- 1 \le k_i \le 10^9
Esimerkki
Syöte:
3 7 3 2 5
Tuloste:
8
Selitys: Kone 1 valmistaa kaksi tuotetta, kone 2 valmistaa neljä tuotetta ja kone 3 valmistaa yhden tuotteen.