CSES - Tehdas
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tehtaassa on nn konetta, joista jokainen valmistaa samaa tuotetta. Tavoitteesi on muodostaa yhteensä tt 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 tt tuotetta?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja tt: koneiden määrä ja tuotteiden määrä.

Seuraavalla rivillä on nn kokonaislukua k1,k2,,knk_1,k_2,\ldots,k_n: kuinka kauan kultakin koneelta kuluu aikaa valmistaa yksi tuote.

Tuloste

Tulosta yksi kokonaisluku: pienin aika, jossa pystyt valmistamaan tt tuotetta.

Rajat

  • 1n51051 \le n \le 5 \cdot 10^5
  • 1t1091 \le t \le 10^9
  • 1ki1091 \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.