Bessie 拿到了 N（1 \leq N \leq 5\times 10 ^ 4）块巧克力。她决定想个办法吃掉这些巧克力，使得它在吃巧克力的这段时间里，最不开心的一天尽可能的开心。并且一共吃 D（1 \leq D \leq 5\times 10 ^ 4）天。

每块巧克力有一个开心值 H_i（1 \leq H_i \leq 10 ^ 6），当某天你吃下那块巧克力时，你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上 Bessie 睡觉之后，它的开心值会减半。也就是说，比如昨天 Bessie 的开心值为 50，那么今天早上一醒来就会有 25 点的开心值，舍去小数点后数字。另外，Bessie 还有一个怪癖，她喜欢按照巧克力本来的排列顺序吃。

Bessie 第一天的开心值为 0，求一个每天吃巧克力的方案，使得 Bessie 最不开心的一天尽可能的开心。

第一行：两个整数 N 和 D，中间用空格分隔。

第 2 行至第 N + 1 行：每行一个整数，第 i + 1 行表示 H_i 的值。

第一行：一个整数，表示 Bessie 在 D 天中最不开心的一天最大可能的开心值。

第 2 至第 n + 1 行，每行一个整数，第 i + 1 行表示 Bessie 吃第 i 块巧克力的日期。

USACO