E. javelins
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a javelin-throwing competition, an athlete faces $$$N$$$ targets arranged in a field, numbered from $$$1$$$ to $$$N$$$. The athlete wants to hit as many targets as possible, but there's a catch: fatigue accumulates with each successful hit.

The athlete has a limited energy budget of $$$B$$$ units. Each target $$$i$$$ has two properties: a base difficulty $$$a_i$$$ and a fatigue coefficient $$$b_i$$$. If target $$$i$$$ is the $$$j$$$-th target hit in sequence, the energy cost to hit it is $$$a_i + (j-1) \cdot b_i$$$.

Your task is to determine the maximum number of targets the athlete can hit without exceeding this energy budget. Note that the athlete can choose any subset of targets and hit them in any order, as long as the total cost doesn't exceed $$$E$$$. Every target can be hit at most once.

Input

The first line contains two integers $$$N$$$ ($$$1 \leq N \leq 10^4$$$) and $$$B$$$ ($$$0 \leq B \leq 10^9$$$) — the number of targets and the energy budget respectively.

The second line contains $$$N$$$ space separated integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \leq a_i \leq 10^5$$$) — the base difficulties for each target.

The third line contains $$$N$$$ space separated integers $$$b_1, b_2, \ldots, b_N$$$ ($$$0\leq b_i \leq 10^5$$$) — the fatigue coefficients for each target.

Output

Output two integers: the maximum number of targets the athlete can hit without exceeding the energy budget $$$B$$$ and the energy required to do so.

Examples
Input
5 12
1 1 1 1 1
1 1 1 1 1
Output
4 10
Input
6 31
11 6 2 14 3 5
14 1 1 1 4 11
Output
4 25