序列加法机

题目信息

时间限制: 1s

空间限制: 256M

输入文件: a.in

输出文件: a.out

题目描述

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

• 选择一个 $1 \leq i \leq n$ 和一个整数 $x$，将 $a_i$ 加上 $x(x$ 可以 $<0)$，操作代价是 $x^2$

并且序列加法机还需要保证每次操作完成后，$a$ 依然是单调不降的，那么序列加法机最少需要多少代价才能将 $a$ 转换成 $b$？

输入格式

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

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

输出格式

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

无解输出 -1

样例

样例输入 1

3 4
1 2 3
2 4 5

样例输出 1

7

数据范围与提示

• $\text{Subtask} 1(10\%): n \leq 3, m, \sum\left|a_i-b_i\right| \leq 10$
• $\text{Subtask} 2(40\%): n, m \leq 300$
• $\text{Subtask}3 (50\%):$ 无特殊限制

对于 $100 \%$ 的数据， $1 \leq n, m \leq 10^5, 0 \leq a_i, b_i \leq 10^9$ ，保证 $\{a\},\{b\}$ 两个序列单调不降。