모자뜨기

매년 전 세계에서는 한달 안에 목숨을 잃는 아기가 $270$만명이고 이중 약 $96$만명이 태어나는 당일에 사망합니다. 직접적 사망 원인은 폐렴이나 설사, 말라리아 혹은 출산합병증 등이지만 신생아 사망을 방지하는 방법은 어렵고 거창한 것이 아닙니다. 탯줄을 자르는 살균된 칼이나, 폐렴을 치료하는 항생제 몇 알, 저체온증을 막아줄 털모자 등으로 충분히 예방과 치료가 가능합니다. 모자뜨기 캠페인을 통해 전달된 털모자는 저체중이나 영양이 부족한 신생아, 조산아들이 따뜻한 체온을 유지하고 생명의 힘을 키울 수 있는 좋은 선물이 되고 있습니다.

이 캠페인에 동참하고자, 넥슨의 직원 $N$명이 모여 신생아들을 돕기 위한 모자뜨기를 할 예정이다. 모든 직원들은 동시에 모자뜨기를 시작한다. 한 직원이 동시에 여러 개의 모자를 뜰 수는 없고, 하나를 다 뜨고 나면 바로 다음 모자를 뜰 수 있다. 직원마다 모자 하나를 뜨는 데 걸리는 시간은 다른데, 모자를 계속 뜬다고 이 시간이 더 느려지거나 빨라지지는 않는다.

바쁜 넥슨 직원들은 모자 $M$개를 최대한 빨리 떠서 캠페인에 전달하려고 한다. 위에서 설명했듯이 사람마다 모자 하나를 뜨는 데 걸리는 시간이 다르기 때문에, 각 직원별로 뜰 모자의 개수를 잘 정해 둬야 일을 빠르게 끝낼 수 있다.

넥슨은 평소 프로그래밍 실력이 뛰어나기로 유명한 당신에게 이 계획을 세워달라고 요청했다. 평소 사회 공헌에 관심이 많은 당신은 기꺼이 도움을 주기로 했다. 최선의 계획을 세웠을 때, 모든 직원이 동시에 모자뜨기를 시작해서 모자 $M$개를 뜨는 데 걸리는 최소 시간을 출력하는 프로그램을 작성하라.

입력 형식

첫째 줄에 직원의 수 $N$($1 \le N \le 1\,000$)과 만들어야 하는 모자의 수 $M$($1 \le M \le 1\,000$)이 공백으로 구분되어 주어진다.

이후 $N$줄에 $i$번째 직원이 모자를 뜨는 데 걸리는 시간 $S_i$ ($1 \le S_i \le 1\,000$)가 주어진다.

출력 형식

첫째 줄에 직원들이 모자 $M$개를 뜨는 데 걸리는 최소 시간을 정수로 출력한다.

예제 1

1 10
30

300

예제 2

2 10
1
11

10

예제 3

2 10
1
9

9

예제 설명

예제 1은 직원이 한 명이므로, $30$분에 하나씩 $10$개를 만들어 $300$분이 걸린다.

예제 2는 직원이 두 명이지만, 작업 시간이 $1$분인 직원이 $10$개를 모두 만드는 경우가 제일 빠르다.

예제 3은 작업 시간이 $1$분인 직원이 $9$개, $9$분인 직원이 $1$개를 만들면 $9$분이 걸린다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설