暂无测试数据。

蒜头君拥有两个长度为 $n$ 的浮点数 数列 $A,B$，每个数列的元素之和为 $1$。现在蒜头君将两个数列上下对齐，然后同时将 $A,B$ 数列划分为的 $k$ 段，保证每段内最少有一个数，且段内数列下标是连续的。例如 $n = 4,k=3$ 时，可以将 $A$ 数列分成 $3$ 段：$\{1,2\},\{3\},\{4\}$ ；$B$ 数列也需要同样的划分，$3$ 段同样为：$\{1,2\},\{3\},\{4\}$。其中 $1,2,3,4$ 表示的是数列中的第几个数。

现在蒜头君定义数列 $A,B$ 每一段的幸运值为该段数字之和。即对于某段所在的区间为 $[l,r]$，那么对于数列 $A$ 该段的幸运值为 $A_l + A_{l+1} + \cdots + A_{r}$；同理也可以计算出数列 $B$ 该段的幸运值为 $B_l + B_{l+1} + \cdots + B_{r}$。

该段的「特殊值」为 $A$ 数列与 $B$ 数列的幸运值之差的绝对值，即：$|(A_l + A_{l+1} + \cdots + A_{r}) - (B_l + B_{l+1} + \cdots + B_{r})|$。

现在蒜头君想要知道，怎么将 $A,B$ 数列同时划分为连续的 $k$ 段，才能保证每段的「特殊值」之和最大。请你帮蒜头君计算出最大的「特殊值」之和。

输入格式

第一行两个整数 $n$ 和 $k$，表示数列的长度为 $n$，要将数列分为 $k$ 段。

第二行 $n$ 个实数，第 $i$ 个数为 $A_i$。

第三行 $n$ 个实数，第 $i$ 个数为 $B_i$。

输出格式

一个实数，表示最大的「特殊值」之和，保留到小数点后六位。

数据范围与约定

• 对于 $30\%$ 的数据：$1\leq n \le 20$。
• 对于 $100\%$ 的数据：$1\leq n \le 800,1\leq k \le 80,k \le n,0\leq A_i,B_i\leq 1,\sum_{i=1}^{n} A_i=1, \sum_{i=1}^{n} B_i=1$。

3 2
0.1 0.75 0.15
0.4 0.3 0.3

0.600000

4 3
0.2 0.3 0.4 0.1
0.2 0.4 0.1 0.3

0.600000