题目背景

众所周知，wld 每天晚上 \(8\) 点睡觉。

题目描述

有一天晚上，wld 要参加一场有 \(n\) 道题的比赛。每道题目有一个难度系数 \(k_i\)。

起初，wld 的疲倦值 \(s\) 为 \(0\)。对于第 \(i\) 道题目，他需要写 \(h_i\) 行代码。wld 写完每行代码的时间为 \(k_i\times(s +1)\) 秒，同时会增加等量的疲倦值。

现在 wld 只想写其中的 \(m\) 道题目，他想知道所需的最短时间是多少。同时由于他是单线程，所以他一次只能同时做一道题，且**在这道题写完之前，他不会去写别的题**。

因为他要赶快做题，所以这个问题交给了你，同时他希望你将答案对 \(252949711\) 取模。

输入格式

第一行两个整数 \(n,m\)。

第二行 \(n\) 个整数 \(k_i\)。

第三行 \(n\) 个整数 \(h_i\)。

输出格式

一行一个整数，表示最终的答案。

样例 #1

样例输入 #1

2 1
1 2
10 5

样例输出 #1

242

提示

由于本题输入数据过大，请使用较快的输入方式。

【样例解释】

对于 样例#1 ，wld 选择做第二道题，花费的时间如下：

• 第 \(1\) 行花费的时间为 \(2\times(0 + 1) = 2\) 秒。
• 第 \(2\) 行花费的时间为 \(2\times(2 + 1) = 6\) 秒。
• 第 \(3\) 行花费的时间为 \(2\times(8 + 1) = 18\) 秒。
• 第 \(4\) 行花费的时间为 \(2\times(26 + 1) = 54\) 秒。
• 第 \(5\) 行花费的时间为 \(2\times(80 + 1) = 162\) 秒。

总时间花费为 \(2 + 6 + 18 + 54 + 162 = 242\) 秒。

由此可见，wld 的状态真的很影响他的做题速度。

【数据范围】

本题采用捆绑测试。

对于 \(100\%\) 的数据，\(1\le m\le n\le10^6\)，\(1\le k\le10^9\)，\(1\le h\le10^{18}\)。

Subtask	\(n\le\)	\(k\le\)	\(h\le\)	分值	特殊性质
\(1\)	\(100\)	\(10\)	\(100\)	\(10\)	\(-\)
\(2\)	\(10^4\)	\(1\)	\(10^6\)	\(10\)	\(-\)
\(3\)	\(10^6\)	\(10^9\)	\(10^{18}\)	\(20\)	\(m=1\)
\(4\)	\(10^6\)	\(10^9\)	\(1\)	\(20\)	\(-\)
\(5\)	\(10^6\)	\(10^9\)	\(10^{18}\)	\(40\)	\(-\)