farfurii

In a housewife's kitchen there is a stack of N plates, numbered from 1 to N, starting with the plate at the top of the stack.
The housewife has to wash the plates, but she has exactly T available minutes. She knows how many minutes are needed for washing each plate. Also, she may break a plate, but 1 minute is needed for breaking it.
At every moment she may take only the plate placed at the top of the stack.
First, she may take the plate 1 (situated at the top of the stack) and wash it or break it). Then, she may take plate 2, and do the same, a.s.o.
The housewife may leave unwashed plates in the stack.

Task

Determine the largest number of plates the hoyusewife can wash in T minutes. Also, determine the minimum time needed to wash a maximum number of plates.

Input data

Input file farfurii.in contains on the first line two integers N T separated by a blank, representing the number of plates and the number of available minutes. The second line contains N integers ts1, ts2, ..., tsN, separated by blanks, representing, in order, the time needed to wash each plate.

Output data

Output file farfurii.out will contain a single line with two integers Nmax and Tmin separated by a blank. Nmax represents the maximum number of plates the housewife can wash in T minutes, and Tmin the minimum time for washing the Nmax plates.

Constraints

0 < N <= 1000
0 < T <= 10000
0 <= tsi<= 100

Example

farfurii.in farfurii.out farfurii.in farfurii.out Explanation
4 4
1 4 1 3 		2 3
 7 11
10 3 2 1 4 2 4 		4 10

For the first example:
She washes plate 1 (1 min), breaks plate 2 (1 min), washes plate 3 (1 min).
For the second example:
She breaks plates 1 and 5 and washes plates 2, 3, 4 and 6.
(Tmin=1+3+2+1+1+2=10)

 

 

 

 

 

Time limit: 0.5 seconds

prof. Dana Lica
Colegiul National “Ion Luca Caragiale” Ploiesti
Contact: danal182001@yahoo.com