自动AC机

题目描述

在一个静谧的晚上，SYOI julao HJX坐在湖边静静地撕烤。

湖边传来丝微的蛤蟆声，隐隐约约月色下出现一位长者，将手中红色包装的盒子放到HJX手里：“我这是作为一名长者，来给你传授一点楞生的经验”。HJX打开盒子一看，竟是无数人梦寐以求的自动AC机。

XPFAOJ上有$n\ (1\leq n\leq1000000)$道题目，而自动AC机的每次最多只能处理$k\ (1\leq k\leq n)$道题，并且切一道题能涨的分为$s[i]\ (0\leq s[i]\leq1000)$。

HJX为了使自己的提交记录看起来不是那么像脚本处理出来的，他打算把OJ上的题目分成几段连续的题让自动AC机处理。HJX为了更进一步的涨分 ，他找来了WHZ来给自己续分数。

WHZ可以通过一些膜法，能把区间$[i,j]$的贡献变为：

但由于XPFAOJ是个辣鸡OJ，它上面会有一些bug，每道题有一个bug值$bug[i] (1\leq bug[i]\leq1000000)$，它会影响HJX的刷分计划 。

若现在自动AC机要刷的这组题为区间$[i,j]$中的题目，那么这组题的总贡献减去$p^2$，其中$p$是小于等于$bug[i-1]$的最大的素数，若bug[i-1]<2，则p=0。

bug[0]=0;

现在HJX想要知道他最多能拿多少分。

由于HJX要去学习LOL 3级放大的技巧，现在他把这个任务交给了你。

输入格式

第一行两个整数$n,k$分别表示有多少道题 最长区间

第二行n个整数$s[i]$表示每道题的得分

第三行n个整数$bug[i]$表示每道题的bug值

输出格式

一个整数 表示最大得分

样例输入

 5 2 



1 2 3 4 5 



5 4 3 2 1  

样例输出

 212 

样例解释

将1,2分一组，贡献为9

将3,4分到一组，贡献为82

将5分到一组，贡献为121

数据范围