Polycarp is given n slabs of coins, each consists of k coins, numbered 1 through k. It takes him tj minutes to pick up the j-th coin of any slab. Thus, time required to pick a coin depends only on its index, but not on the slab itself. Polycarp can pick up coins in any order.

By picking up the coin of any slab he earns one point. Thus, the number of points for a slab is equal to the number of picked coins in it. Moreover, if Polycarp picks all k coins of a slab, he recieves one extra point. Polycarp has M minutes of time. What is the maximum number of points he can earn? 1 ≤ n ≤ 45 1 ≤ k ≤ 45 0 ≤ M ≤ 2·10^9 1 ≤ tj ≤ 1000000