농부 존은 최근에 소 도서관을 위해 새로운 책장을 구입했는데, 책들이 워낙 빠른 속도로 채워져서 이제 남은 것은 가장 위에 있는 공간뿐이다.

존은 N (1≤N≤20,000)마리의 소를 데리고 있고, 각각의 소의 키는 H_i(1≤H_i≤10,000)이다. 책장의 높이는 B(1≤B≤S<2,000,000,007)이다. 여기서 S는 모든 소들의 키의 합을 의미한다.

책장의 꼭대기에 닿기 위해서, 한 마리 이상의 소가 아래에 있는 소를 밟고 올라서게 된다. 이 때 소들의 총 높이는 각 소들의 키의 합이다. 꼭대기에 닿으려면 총 높이가 최소한 책장의 높이만큼은 되어야 한다.

필요 이상으로 많은 소들이 올라가게 되면 위험할 수 있기 때문에, 존은 최소의 소들만 사용하여 책장에 닿을 수 있게끔 하려고 한다. 소들이 책장의 높이 이상으로 올라서면서 소의 숫자가 최소로 되도록 하자.

책 꺼내기 Part1 timer 1s memory - MB

책 꺼내기 Part1 1s - MB