By Alisson Soares, UECE Brazil
Bile is a smart kid who likes quite recurrences. He was participating in a competition in which the best sequence wins a prize. Bile created a sequence F, in the sequence, the first N values are known, and to discover the value of Fk for a K N is used to formulate below.
For N K: FK = 1*FK-1 + 2*FK-2 + ... + N*FK-N
But he does not know calculate quickly the values of their sequence and asked for your help.
In the first test case: N = 2, K = 3, F1 = 2, F2 = 5, F3 = F2 + 2*F1 = 9, F4 = F3 + 2*F2 = 19 ...
The input consists of several test cases. Each test case consists of two lines. The first line of each test case contains two integers, N ( 2 ≤ N ≤ 100 ) and K ( N ≤ K ≤ 1018 ), representing the number of values of the first known sequence Bile. The second line consists of N integers Fi ( F1, F2, … ,FN ) and ( 0 ≤ Fi ≤ 1010 ) representing the values initially known. The entry ends with the final file (EOF).
For each test case you should to print the value FK and the sum of all elements of bile function minor or equal to FK, separated by a single space. Your answers should be submitted in module 303700049.
|Input Sample||Output Sample|