题目描述

在一年一度的全国爱猫日庆祝活动中成功阻止了猫的灭绝后，猫 Ket 现在收到了来自食猫王国的饥饿投诉。因此，Ket 被委派去运送食物，以防止它们再次诉诸同类相食。

这个猫王国可以被建模为一条从西向东延伸的漫长道路。道路的西端有一个食物银行。食物银行以东有 $n$ 间猫屋，编号从 $1$ 到 $n$。保证 $n$ 是 偶数。第一间房子位于食物银行以东 $d[1]$ 公里处。对于 $i \geq 2$，第 $i$ 间房子位于第 $(i - 1)$ 间房子以东 $d[i]$ 公里处。

Ket 将驾驶一辆送货车向这些房子运送食物。卡车从食物银行出发，初始拥有 $x$ 单位的燃料。1 单位燃料允许 Ket 驾驶他的卡车沿道路行驶 1 公里。

第 $i$ 间房子有 $f[i]$ 单位的燃料可供卡车使用。卡车拥有无限的燃料存储空间，并且只在燃料耗尽时才会停下。卡车离开后无需返回食物银行。

:::align{center} :::

此外，Ket 拥有一根魔杖。挥动一次魔杖，他可以 交换 第 $i$ 间和第 $(n - i + 1)$ 间猫屋中储存的燃料量。只有当两个房子中的燃料都尚未被使用时，才能进行此交换。请帮助 Ket 找到他使用任意次数交换后能够到达的最远房子的索引 $D$。同时，请帮助 Ket 找到到达房子 $D$ 所需的最小交换次数 $S$。

你可以参考样例测试 #1 以获得更详细的解释。

输入格式

你的程序需要从标准输入读取数据。

输入的第一行包含两个由空格分隔的整数 $n$ 和 $x$。

输入的第二行包含 $n$ 个由空格分隔的整数 $d[1], d[2], \dots, d[n]$。

输入的第三行包含 $n$ 个由空格分隔的整数 $f[1], f[2], \dots, f[n]$。

输出格式

你的程序需要向标准输出写入数据。

在一行中输出 两个 由空格分隔的整数。第一个整数应为 $D$，即 Ket 能到达的最远房子的索引，接着是 $S$，即到达房子 $D$ 所需的最小交换次数。

6 1
1 1 3 1 1 6
1 1 1 4 3 2

5 1

6 5
3 8 3 1 4 1
2 7 1 6 2 7

6 1

6 2
2 24 25 40 5 11
4 12 14 16 20 30

3 2

6 10
3 6 3 7 8 6
4 3 1 7 1 6

5 1

提示

样例测试 #1 解释

:::align{center} :::

有一个食物银行，其东边有 $n = 6$ 间房子。Ket 的卡车以 $x = 1$ 单位燃料出发，行驶到房子 $1$。然后他在房子 $1$ 补充燃料，并行驶到房子 $2$。此时，Ket 最优的做法是使用他的魔杖交换房子 $2$ 和房子 $5$ 的燃料量，这使他能够补充 $3$ 单位燃料并到达房子 $3$。随后，他可以在前往接下来两间房子的途中补充 $1$ 单位燃料，并分别在房子 $4$ 和房子 $5$（由于之前的交换）补充 $4$ 单位和 $1$ 单位燃料。

之后他将剩下 $4$ 单位燃料，这使他无法前往房子 $6$，因为那需要 $6$ 单位燃料。由于 Ket 在到达房子 $6$ 之前耗尽了燃料，他只能到达房子 $5$。此外，他必须使用魔杖进行一次交换。因此，$D = 5$ 且 $S = 1$。

子任务

对于所有测试用例，输入数据满足以下限制：

• $2 \leq n \leq 500\,000$
• $n$ 是偶数。
• 对于所有 $1 \leq i \leq n$，有 $1 \leq d[i] \leq 10^9$
• 对于所有 $1 \leq i \leq n$，有 $1 \leq f[i] \leq 10^9$
• $d[1] \leq x \leq 10^9$

你的程序将在满足以下限制的输入实例上进行测试：

注意：一个数 $x$ 的绝对值，记作 $\vert x \vert$，是 $0$ 与 $x$ 在数轴上的距离的非负数。例如，$\vert 5 \vert = 5$ 且 $\vert -5 \vert = 5$。

翻译由 DeepSeek V3.2 完成