题目描述

小明正在玩一个闯关游戏。地图上有 $n$ 个平台，第 $i$ 个平台都有一个高度 $h_i$ 和一个奖励 $a_i$，如果小明跳到第 $i$ 个平台就可以拿到 $a_i$ 的奖励。

小明需要从第 $1$ 个平台出发，最终到达第 $n$ 个平台，为了加大难度，红红给他设置了两个限制：

• 只有当 $1\le j-i\le k$ 时，才能从平台 $i$ 跳到平台 $j$（不会回头或者原地跳，往后最多只能跳到第 $i+k$ 个平台）。
• 只有当 $|h_i-h_j|$ 不超过小明的跳跃能力时，才能从平台 $i$ 跳到平台 $j$。（$|a|$ 表示 $a$ 的绝对值，可以通过 C++ 的 abs(x) 函数计算）

请回答两个问题：

1. 如果小明跳跃能力无限，那么他最多能拿到多少奖励？
2. 为了拿到最多的奖励，小明的跳跃能力最小是多少？

输入格式

第一行为空格隔开的两个整数：$n,k$。

第二行为空格隔开的 $n$ 个整数：$a_1\sim a_n$。

第三行为空格隔开的 $n$ 个整数：$h_1\sim h_n$。

输出格式

输出两行，每行都是一个整数。分别是两个问题的答案。

10 2
1 -1 -2 -10 5 -5 -5 -5 -5 0
5 5 5 5 5 100 6 7 3 2  

-6
3

样例解释 1

如果跳跃能力无限，能达成的最大奖励是：$1+(-2)+5+(-5)+(-5)+0=(-6)$

要达成这个最大奖励，跳跃能力最小为：$3$，途经平台是：1,3,5,7,8,10

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,k \le 5000$，$-10^9\le a_i,h_i\le 10^9$。

• 子任务 1（30 分）：保证所有平台高度都相等，$h_i$ 相同。
• 子任务 2（30 分）：保证所有平台奖励都相同，$a_i$ 相同。
• 子任务 3（40 分）：没有特殊限制。