gxy 的积木高塔 1596

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：14 AC：2 Score：100

Description

gxy 有 $n$ 块积木，每块积木的高度都相同，但是底面面积不同，第 $i$ 块积木的底面面积为 $w_i$

现在 gxy 用这些积木来搭一个 $k$ 层高的高塔，每一层只用一块积木，而为了高塔的稳定，对于相邻两层的积木来说，下层积木的底面面积必须是上层积木的两倍以上

现在 gxy 想知道，自己最多能搭几个 $k$ 层的高塔？

Input

第一行两个正整数 $n,k$，分别表示积木的块数，以及高塔的层数。

第二行 $n$ 个正整数 $w_i$，分别表示每块积木的底面面积。

对于 $30\%$ 的数据满足:$n,k \leq 7$

对于 $100\%$ 的数据满足:$2 \leq n \leq 2 * 10^5, 2 \leq k \leq 30, k \leq n, 1 \leq w_i \leq 2^{31}$

Output

输出一行一个整数，表示最多可搭建的高塔的个数。

Samples

input:

9 3 6 1 11 4 8 7 2 18 3

output:

Hint

其中一组方案，两个高塔分别是：{$1\ 2\ 4$},{$3\ 7\ 18$}