Sagheer and Nubian Market

Luxor and Aswan로 여행을 떠난 Sagheer는 친구들과 친척들에게 줄 기념품을 사기 위해 Nubian 시장에 갔다. 이 시장에는 몇 가지 이상한 규칙이 있다. 시장에는 1부터 n까지 번호가 매겨진 n개의 서로 다른 상품이 있다. i-th번째 상품의 기본 가격은 ai Egyptian 파운드이다. If Sagheer가 인덱스가 x1, x2, ..., xk인 k개의 상품을 산다면, 1 ≤ j ≤ k인 상품 xj의 가격은 axj + xj·k이다. 다시 말해, 상품의 가격은 기본 가격에 그 상품의 인덱스와 계수 k를 곱한 값을 더한 것과 같다.

Sagheer는 S Egyptian파운드를 초과하여 지불하지 않으면서 가능한 한 많은 기념품을 사고 싶어 한다. 같은 기념품을 두 번 이상 살 수 없다는 점에 유의한다. 기념품의 개수를 최대로 만드는 방법이 여러 가지라면, 총비용이 최소가 되는 방법을 선택한다. 이 일을 도와주자.

첫째 줄에 정수 n와 S (1 ≤ n ≤ 105 and 1 ≤ S ≤ 109)가 주어진다. 각각 시장에 있는 기념품의 개수와 Sagheer의 예산을 나타낸다.

둘째 줄에 공백으로 구분된 정수 n개, a1, a2, ..., an (1 ≤ ai ≤ 105)이 주어진다. 기념품들의 기본 가격을 나타낸다.

한 줄에 두 정수 k, T를 출력한다. 각각 Sagheer가 살 수 있는 기념품의 최대 개수와 이 k개의 기념품을 사는 데 필요한 최소 총비용을 나타낸다.

첫 번째 예제에서 세 상품의 가격은 총 28이 되는 $[5, 9, 14]$이므로 세 상품을 모두 고를 수 없다. 두 상품만 고르기로 하면 가격은 $[4, 7, 11]$이 된다. 따라서 첫 번째와 두 번째 상품을 살 수 있다.

두 번째 예제에서는 모든 상품의 가격이 $[5, 10, 17, 22]$이므로 모든 상품을 살 수 있다.

세 번째 예제에서는 시장에 기념품이 하나뿐이며 그 가격은 8파운드이므로 살 수 없다.