题目描述

某老板打算从n个地点中选择合适的位置开一些餐馆。这n个地点排列在同一条直线上，用一个递增的整数序列mi来表示它们的位置。由于地段关系, 开餐馆的利润会有所不同，用pi表示在i处开餐馆的利润。

为了避免自己的餐馆的内部竞争，餐馆之间的距离必须大于k。

请你编程计算一个总利润最大的方案，输出总利润。

输入格式

第一行两个整数n(1≤n≤100)代表地点的数量，k代表餐馆距离(1≤k≤1000)的最小值；

第二行n个递增的正整数，代表n个地点的位置mi(1≤mi≤1000)；

第三行n个的正整数，代表n个地点的餐馆利润pi(1≤pi≤100)。

输出格式

一个整数，表示最大总利润。

输入/输出样例

3 11
1 2 15
10 2 30

40

3 16
1 2 15
10 2 30

30

说明/提示

时间1000ms，内存256MiB