CSES - Factory Machines | Máy trong xưởng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pypy 3 5.0s
Python 3 5.0s
Tác giả:
tan , Flower_On_Stone , Lephuchieuzz
Dạng bài
Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một xưởng có \(n\) máy có thể được sử dụng để làm sản phẩm. Mục tiêu của bạn là tạo ra tổng cộng \(t\) sản phẩm.

Đối với mỗi máy, bạn biết số giây cần thiết để tạo ra một sản phẩm duy nhất. Các máy có thể hoạt động đồng thời, và bạn có thể tự do quyết định lịch trình của chúng.

Thời gian cần thiết ngắn nhất để tạo ra \(t\) sản phẩm là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(t\): số lượng máy và sản phẩm.
  • Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): thời gian cần thiết để tạo ra một sản phẩm bằng mỗi máy.

Output

  • In một số nguyên: thời gian tối thiểu cần thiết để tạo ra \(t\) sản phẩm.

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le t \le 10^9\)
  • \(1 \le a_i \le 10^9\)

Example

Sample input

3 7
3 2 5

Sample output

8

Note

Máy \(1\) làm hai sản phẩm, máy \(2\) làm bốn sản phẩm và máy \(3\) làm một sản phẩm.

Bình luận