题目描述

有一个“序列加法机”，它的作用是把一个长度为 $n$ 的单调不降序列 $a$ 转换成另一个长度为 $n$ 的单调不降序列 $b$。不过由于序列加法机的功能还不完善，现在它只能执行不超过 $m$ 次以下操作：

选择一个 $1\le i\le n$ 和一个整数 $x$，将 $a_i$ 加上 $x$（$x$ 可以 $<0$），操作代价是 $x^2$，并且序列加法机还需要保证每次操作完成后，$a$ 依然是单调不降的。那么序列加法机最少需要多少代价才能将 $a$ 转换成 $b$？

输入格式

第一行，两个正整数 $n,m$。

接下来两行，每行 $n$ 个数，分别表示 $a$ 和 $b$。

输出格式

一个数，表示最小代价，对 $998244353$ 取模。

无解输出 $-1$。

样例

3 4
1 2 3
2 4 5

7

5 3
1 4 8 11 13
2 3 9 11 12

-1

5 2
1 7 11 15 22
2 7 11 18 22

10

说明/提示

数据规模与约定

• 对于 $10\%$ 的数据，$n \le 5$， $m, \sum |a_i - b_i| \le 10$
• 对于 $50\%$ 的数据，$n,m \le 300$
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$0 \le a_i, b_i \le 10^9$，保证 $\{a\}$，$\{b\}$ 两个序列单调不降