On his trip to Luxor and Aswan, Sagheer went to a Nubian market to buy some souvenirs for his friends and relatives. The market has some strange rules. It contains n different items numbered from 1 to n. The i-th item has base cost a_{i} Egyptian pounds. If Sagheer buys k items with indices x_1, x_2, ..., x_{k}, then the cost of item x_{j} is a_{x}_{j} + x_{j}·k for 1 ≤ j ≤ k. In other words, the cost of an item is equal to its base cost in addition to its index multiplied by the factor k.

Sagheer wants to buy as many souvenirs as possible without paying more than S Egyptian pounds. Note that he cannot buy a souvenir more than once. If there are many ways to maximize the number of souvenirs, he will choose the way that will minimize the total cost. Can you help him with this task?


-----Input-----

The first line contains two integers n and S (1 ≤ n ≤ 10^5 and 1 ≤ S ≤ 10^9) — the number of souvenirs in the market and Sagheer's budget.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5) — the base costs of the souvenirs.


-----Output-----

On a single line, print two integers k, T — the maximum number of souvenirs Sagheer can buy and the minimum total cost to buy these k souvenirs.


-----Examples-----
Input
3 11
2 3 5

Output
2 11

Input
4 100
1 2 5 6

Output
4 54

Input
1 7
7

Output
0 0



-----Note-----

In the first example, he cannot take the three items because they will cost him [5, 9, 14] with total cost 28. If he decides to take only two items, then the costs will be [4, 7, 11]. So he can afford the first and second items.

In the second example, he can buy all items as they will cost him [5, 10, 17, 22].

In the third example, there is only one souvenir in the market which will cost him 8 pounds, so he cannot buy it.

Difficulty: interview

Starter code:

Solutions:
def check(k):
    anew = [a[i] + (i + 1) * k for i in range(n)]
    anew.sort()
    asum = sum(anew[:k])
    if asum <= s:
        return asum
    else:
        return 0


n, s = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
min_sum = 0
L = 0
R = n + 1
while R - L > 1:
    m = (L + R) // 2
    res = check(m)
    if res:
        L = m
        min_sum = res
    else:
        R = m
print(L, min_sum)


n, S = list(map(int, input().split()))
a = [int(x) for x in input().split()]

def calc(k):
    prices = [a[i] + (i + 1) * k for i, x in enumerate(a)]
    prices.sort()
    return sum(prices[:k])

l, r = 0, n
while l != r:
    m = (l + r + 1) // 2
    if calc(m) <= S:
        l = m
    else:
        r = m - 1

print(l, calc(l))


n, s = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))


def tr(m):
    bb = [x + (i+1)*m for (i,x) in enumerate(b)]
    bb = sorted(bb)
    res = sum(bb[:m])

    if res <= s:
        return res
    else:
        return None


res = None
lo = 0
hi = n

d = {}
maxgood = -1

while lo < hi:
    mid = (lo+hi)//2
    #print("\nl m h", lo, mid, hi)
    temp = tr(mid)
    d[mid] = temp
    if temp is not None:
        lo = mid+1
        maxgood = max(maxgood, mid)
    else:
        hi = mid
    #print("new l m h", lo, mid, hi, "\n")

temp = tr(hi)
d[hi] = temp
if temp is not None:
    maxgood = max(maxgood, hi)

temp = tr(lo)
d[lo] = temp
if temp is not None:
    maxgood = max(maxgood, lo)

temp = tr(mid)
d[mid] = temp
if temp is not None:
    maxgood = max(maxgood, mid)

print(maxgood, d[maxgood])


def good(k):
    newp = []
    for i in range(len(prices)):
        newp.append(prices[i] + (i + 1) * k)
    newp.sort()
    mincosts[k] = sum(newp[:k])
    return mincosts[k] <= s


def binsearch():
    l = 0
    r = n + 1
    while r - l > 1:
        m = (l + r) // 2
        if good(m):
            l = m
        else:
            r = m
    if r < n + 1 and good(r):
        return r
    return l

n, s = map(int, input().split())
prices = list(map(int, input().split()))
mincosts = [0 for i in range(n + 1)]

b = binsearch()
print(b, mincosts[b])

def proverka(k, a, s):
    b = []
    for i in a:
        b.append(i)
    for i in range(len(b)):
        b[i] = b[i] + k * (i + 1)
    b.sort()
    cnt = 0
    index = 0
    while(cnt < k and s - b[index] >= 0):
        cnt += 1
        s -= b[index]
        index += 1
    if(cnt < k):
        return False
    else:
        return True
n, s = list(map(int, input().split()))
a = list(map(int, input().split()))
l = 0
r = n + 1
while(l + 1 < r):
    if(proverka((l+r)//2, a, s)):
        l = (l+r)//2
    else:
        r = (l+r)//2
for i in range(n):
    a[i] = a[i] + l * (i + 1)
a.sort()
qwer = 0
index = 0
while(index < l and qwer + a[index] <=  s):
    qwer += a[index]
    index += 1
print(l, qwer)


import sys
from itertools import accumulate

def solve():
    def check(m):
        if m == 0:
            return 0

        b = [ai + (i + 1)*m for i, ai in enumerate(a)]
        b.sort()

        return sum(b[:m])

    n, S = map(int, input().split())
    a = [int(i) for i in input().split()]

    btm = -1
    top = n + 1

    while top - btm > 1:
        mid = (top + btm) // 2

        if check(mid) <= S:
            btm = mid
        else:
            top = mid

    k = btm
    T = check(k)

    print(k, T)

def __starting_point():
    solve()
__starting_point()

def func(c,k,s,n):
	nc=[]
	for i in range(n):
		nc.append(c[i]+(i+1)*(k+1))
	nc.sort()
	val=sum(nc[:k+1])
	if(val<=s):
		return val
	else:
		return -1

inp=input().split()
n=int(inp[0])
s=int(inp[1])
c=[]
val=input().split()
i=1
for v in val:
	c.append(int(v))
	i+=1
begin=0
end=n-1
flag=0
while(begin<=end):
	mid=(begin+end)//2
	if(func(c,mid,s,n)!=-1):
		if(mid==n-1):
			print(mid+1,func(c,mid,s,n))
			flag=1
			break
		if(func(c,mid+1,s,n)==-1):
			print(mid+1,func(c,mid,s,n))
			flag=1
			break
		else:
			begin=mid+1
	else:
		end=mid-1
if(flag==0):
	print("0 0")



import sys

def main():
    n,s = map(int,sys.stdin.readline().split())

    a = list(map(int, sys.stdin.readline().split()))
    
    l= 0
    r = n

    bestk =0
    bests = 0
    while l<r:
        mid = (l+r)//2
        x = [a[i]+(i+1)*mid for i in range(n)]
        x.sort()
        t = 0
        for i in range(mid):
            t+=x[i]
        if t<=s:
            bests = t 
            bestk = mid
            l = mid+1
        else:
            r = mid-1
    mid = l
    x = [a[i]+(i+1)*mid for i in range(n)]
    x.sort()
    t = 0
    for i in range(mid):
        t+=x[i]
    if t<=s:
        bestk = mid 
        bests = t

    print(bestk, bests)

main()

def canBuy(k):
	fullCost = [(i + 1) * k + cost[i] for i in range(0, n)]
	fullCost = sorted(fullCost)
	fullSum = sum(fullCost[:k])
	return fullSum <= money

def canBuyCost(k):
	fullCost = [(i + 1) * k + cost[i] for i in range(0, n)]
	fullCost = sorted(fullCost)
	fullSum = sum(fullCost[:k])
	return fullSum if fullSum <= money else -1

n, money = [int(x) for x in input().split()]
cost = [int(x) for x in input().split()]

left = 0
right = n
while left < right - 1:
	mid = (left + right) // 2
	if canBuy(mid):
		left = mid
	else:
		right = mid

rightRes = canBuyCost(right)
if rightRes == -1:
	print(left, canBuyCost(left))
else:
	print(right, rightRes)

from sys import stdin


def cost_of(data, k):
    kl = []
    for index, item in enumerate(data):
        kl.append(item + (index + 1) * k)
    kl.sort()

    accu = 0
    for i in range(0, k):
        accu += kl[i]

    return accu


n, s = list(map(int, stdin.readline().rstrip().split()))
data = list(map(int, stdin.readline().rstrip().split()))
left, right = 0, n
cleft, cright = 0, cost_of(data, n)

if s >= cright:
    print("{0} {1}".format(n, cright))
    return

last_center = -1
center = -1
while left <= right:
    last_center = center
    center = (left + right) // 2
    ccenter = cost_of(data, center)

    if center == last_center:
        rs = right if s >= cright else left
        left = rs
        break
    if s < ccenter:
        right = center - 1
        cright = cost_of(data, right)
    else:
        left = center
        cleft = cost_of(data, left)

print(left, cost_of(data, left))


from itertools import count

n, m = list(map(int, input().split()))
p = [int(num) for num in input().split()]


def calc(cnt):
    new_p = list(map(lambda ind, num: num + cnt * ind, count(1), p))
    return sum(sorted(new_p)[:cnt])


def can(cnt):
    return calc(cnt) <= m


l = 0
r = n + 1
while r - l > 1:
    mid = (l + r) // 2
    if can(mid):
        l = mid
    else:
        r = mid

print(l, calc(l))


from sys import stdin


def check(n, s, a):
    a.sort(key=lambda x: x[1] * n + x[0])
    r = 0
    for i in a[:n]:
        r += i[0] + i[1] * n
    return r


def main():
    n, s = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    for i in range(n):
        a[i] = [a[i], i + 1]
    l = 0
    res = 0
    r = n + 1
    while r - l > 1:
        m = (l + r) // 2
        b = a[:]
        res_new = check(m, s, b)
        if res_new <= s:
            l = m
            res = res_new
        else:
            r = m
    print(l, res)


main()

import sys
n, s = list(map(int, sys.stdin.readline().split()))
l = list(map(int, sys.stdin.readline().split()))
t = list([x[1] + n * (x[0]+1) for x in enumerate(l)])
upper = n-1
lower = 0
while upper > lower:
    k = (upper + lower) // 2
    # print("u",upper,'l',lower)
    t = list([x[1] + k * (x[0] + 1) for x in enumerate(l)])
    h = sum(sorted(t)[:k])
    if h == s:
        break
    if h < s:
        lower = k + 1
    else:
        upper = k - 1

t = list([x[1] + upper * (x[0] + 1) for x in enumerate(l)])
if sum(sorted(t)[:upper]) <= s:
    z = list([x[1] + (upper + 1) * (x[0] + 1) for x in enumerate(l)])
    if sum(sorted(z)[:upper+1]) <s:
        print(upper+1, sum(sorted(z)[:upper+1]))
    else:
        print(upper, sum(sorted(t)[:upper]))
else:
    t = list([x[1] + (upper-1) * (x[0] + 1) for x in enumerate(l)])
    print(upper-1, sum(sorted(t)[:upper-1]))



n,s = map(int, input().split())
a = list(map(int, input().split()))

def check(m):
    ac = sorted([a[i-1] + i*m for i in range(1,n+1)])
    w = sum(ac[:m])
    if w <= s:
        return True, w
    else:
        return False, 0

l,r = 0, len(a) + 1
last = -1
lastw = 0
while l < r:
    m = l + (r - l)//2
    st, w = check(m)
    if st:
        last = m
        lastw = w
        if l == m:
            break
        l = m
    else:
        r = m
print(last, lastw)

def f(k):
    cur = sum(sorted([a[i] + (i + 1) * k for i in range(n)])[:k])
    return cur, cur <= S
read = lambda: map(int, input().split())
n, S = read()
a = list(read())
l, r = 0, n + 1
while r - l > 1:
    m = (l + r) >> 1
    if f(m)[1]: l = m
    else: r = m
print(l, f(l)[0])

def calc(cnt):
    return sum(sorted(num + cnt * ind for ind, num in enumerate(price, 1))[:cnt])

n, money = list(map(int, input().split()))
price = [int(num) for num in input().split()]

can = 0
cant = n + 1
while cant - can > 1:
    mid = (can + cant) // 2
    if calc(mid) <= money:
        can = mid
    else:
        cant = mid

print(can, calc(can))


from sys import stdin as fin
# fin = open("cfr417c.in", "r")

n, S = map(int, fin.readline().split())
arr = list(map(int, fin.readline().split()))

def test(k):
    nonlocal arr, n, S
    costs = sorted([arr[i] + (i+1)*k for i in range(n)])
    csum = sum(costs[:k])
    # print(costs)
    if csum <= S:
        return csum
    else:
        return 0

l, r, m = 0, n + 1, 0
ans, ansm = 0, 0
while l + 1 != r:
    m = (l + r) // 2
    # print(l, r, m)
    csum = test(m)
    if not csum:
        r = m
    else:
        ans = csum
        ansm = m
        l = m
print(ansm if ans else 0, ans)

n,s=[int(i) for i in input().split()]
ll=[int(i) for i in input().split()]
curr=0;
l=0
h=n
while l<=h :
	mid = (h+l)//2;
	k=ll[:]
	for i in range(n):k[i]=(i+1)*mid+ll[i];
	k.sort();
	#print(k)
	sm=sum(k[:mid])
	#print(mid,sm)
	if sm<=s:
		curr=mid
		l=mid+1
		ans=sm
	else:
		h=mid-1
print(curr,ans)

def newArr(a, k):
    b = a
    i = 0
    n = len(a)
    while i < n:
        b[i] += (i+1)*k
        i += 1
    return b

def minSum(a, k):
    a.sort()
    sm = 0
    cnt = 0
    i = 0
    while i < k:
        sm += a[i]
        i += 1
    return sm


inp = input().split()
n = int(inp[0])
S = int(inp[1])
inp = input().split()
a = []
for x in inp:
    a.append(int(x))
l = 0
r = n
while l<r:
    mid = (l+r)//2
    if l+1 == r:
        mid = r
    b = newArr(list(a), mid)
    if minSum(b, mid) <= S:
        l = mid
    else:
        r = mid - 1
ans = l
print(str(ans) + ' ' + str( minSum(newArr(a, ans), ans) ))


n, S = map(int, input().split())
a = list(map(int, input().split()))
l, r, m, cost = 0, n + 1, -1, -1
while r - l > 1:
  m = (l + r) // 2
  cost = sum(sorted([a[i] + (i + 1) * m for i in range(n)])[:m])
  l, r = ((l, m) if cost > S else (m, r))
print(l, sum(sorted([a[i] + (i + 1) * l for i in range(n)])[:l]))

from sys import stdin
inFile = stdin
tokens = []
tokens_next = 0

def next_str():
    nonlocal tokens, tokens_next
    while tokens_next >= len(tokens):
        tokens = inFile.readline().split()
        tokens_next = 0
    tokens_next += 1
    return tokens[tokens_next - 1]

def nextInt():
    return int(next_str())

def min_cost(a, k):
    if k > len(a):
        return False

    new_a = [a[i] + (i + 1) * k for i in range(len(a))]
    new_a = sorted(new_a)
    return sum(new_a[:k])

n = nextInt()
S = nextInt()
a = [nextInt() for _ in range(n)]

low = 0
high = n + 1
while low + 1 < high:
    mid = (low + high) // 2
    if min_cost(a, mid) <= S:
        low = mid
    else:
        high = mid

print(low, min_cost(a, low)) 

from sys import stdin
inFile = stdin
tokens = []
tokens_next = 0

def next_str():
    nonlocal tokens, tokens_next
    while tokens_next >= len(tokens):
        tokens = inFile.readline().split()
        tokens_next = 0
    tokens_next += 1
    return tokens[tokens_next - 1]

def nextInt():
    return int(next_str())

from heapq import heapify, heappop
def min_cost(a, k):
    if k > len(a):
        return False

    new_a = [a[i] + (i + 1) * k for i in range(len(a))]
    heapify(new_a)
    s = 0
    for _ in range(k):
        s += heappop(new_a)
    return s

n = nextInt()
S = nextInt()
a = [nextInt() for _ in range(n)]

low = 0
high = n + 1
while low + 1 < high:
    mid = (low + high) // 2
    if min_cost(a, mid) <= S:
        low = mid
    else:
        high = mid

print(low, min_cost(a, low)) 

#!/usr/bin/env python3


n, S = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

lo, hi = 0, n + 1
while lo < hi:
    mid = (lo + hi) // 2
    if mid > n:
        hi = mid
        continue
    if sum(sorted(x + (i + 1) * mid for i, x in enumerate(a))[:mid]) <= S:
        lo = mid + 1
    else:
        hi = mid
lo -= 1
print(lo, sum(sorted(x + (i + 1) * lo for i, x in enumerate(a))[:lo]))


n,s = list(map(int,input().split()))
arr = list(map(int,input().split()))

def buy(k):
    nonlocal n,s,arr
    if k==0:
        return 0
    temp = sorted([arr[i-1]+i*k for i in range(1,n+1)])
    return sum(temp[:k])

def main():


    f,l = 0,n
    while f<l:
        if f==l-1:
            a,b=buy(f),buy(l)
            return (l,b) if b<=s else (f,a)
        m = (f+l)//2
        if buy(m)<=s:
            f=m
        else:
            l=m

a,b=main()
print(a,b)


n,s = list(map(int,input().split()))
arr = list(map(int,input().split()))

from heapq import heapify, heappop

def buy(k):
    nonlocal n,s,arr
    if k==0:
        return 0
    ans = 0 
    temp = [arr[i-1]+i*k for i in range(1,n+1)]
    heapify(temp)
    for i in range(k):
        ans += heappop(temp)
    return ans

def main():


    f,l = 0,n
    while f<l:
        if f==l-1:
            a,b=buy(f),buy(l)
            return (l,b) if b<=s else (f,a)
        m = (f+l)//2
        if buy(m)<=s:
            f=m
        else:
            l=m

a,b=main()
print(a,b)