大胃王比赛

题目描述

高桥君决定参加大胃王比赛。这场比赛是以 $N$ 人为单位的团队赛，高桥君的团队由按年龄顺序编号为 $1$ 到 $N$ 的 $N$ 名成员组成。成员 $i$ 的消化成本为 $A_i$。

比赛准备了编号为 $1$ 到 $N$ 的 $N$ 个食物，食物 $i$ 的难吃程度为 $F_i$。比赛规则如下：

• 每个食物分配 $1$ 名团队成员。不能将同一名成员分配给多个食物。
• 对某名成员，当其消化成本为 $x$、所负责食物的难吃程度为 $y$ 时，吃完该食物需要 $x \times y$ 秒。
• $N$ 名成员各自吃完所负责食物所需时间中的最大值，即为团队的整体成绩。

比赛之前，高桥君的团队决定进行修行。只要自己的消化成本不为负数，每修行 $1$ 次，成员可以将自己的消化成本减少 $1$。但是，由于修行需要花费巨额伙食费，$N$ 人合计最多只能修行 $K$ 次。

当合适地选择各成员的修行次数和所负责的食物时，团队的整体成绩最小可以是多少呢？

输入格式

输入按以下格式从标准输入给出：

$N$ $K$
$A_1$ $A_2$ $...$ $A_N$
$F_1$ $F_2$ $...$ $F_N$

输出格式

输出团队整体成绩的最小值。

样例

3 5
4 2 1
2 3 1

2

按如下安排，团队整体成绩为 $2$。

• 让成员 $1$ 修行 $4$ 次，分配食物 $2$。吃完所需时间为 $(4-4) \times 3 = 0$ 秒。
• 让成员 $2$ 修行 $1$ 次，分配食物 $3$。吃完所需时间为 $(2-1) \times 1 = 1$ 秒。
• 让成员 $3$ 修行 $0$ 次，分配食物 $1$。吃完所需时间为 $(1-0) \times 2 = 2$ 秒。

团队整体成绩无法小于 $2$，所以答案是 $2$。

3 8
4 2 1
2 3 1

0

不一定必须正好修行 $K$ 次。

11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2

12

数据范围

• 输入均为整数
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq K \leq 10^{18}$
• $1 \leq A_i \leq 10^6$（$1 \leq i \leq N$）
• $1 \leq F_i \leq 10^6$（$1 \leq i \leq N$）