A5119 | $午枫的陪伴时间$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小枫工作后越来越忙，陪伴小午的时间也越来越少了，为了维持两人的感情小枫打算多抽出点时间来陪伴小午，小枫每次陪小午只能连续陪正好 $t$ 天。 小午现在给了小枫 $n$ 个选项，第 $i$ 个选项的内容为小枫第 $a_i$ 天开始陪他，即小枫需要从第 $a_i$ 开始陪到第 $a_i+t-1$ 天。小枫在陪伴小午的过程中，无法再选择小午给出的其他在这个时间段的上的选项（包括开头和结尾）。 现在小枫需要对小午的每个选项做出选择，如果小枫没选择小午的第 $i$ 个选项，就要给他买一个价值 $v_i$ 的礼物；如果小枫选择完成小午的第 $i$ 个选项，小枫就会花费 $cost_i$ 元陪他度过一段愉快的时光。 现在小枫要通过合理的安排使得最后的花费最少。他想知道最少花费是多少。

第一行输入两个正整数 $n,t$ $(1\leq t\leq n\leq 10^6)$ ，分别表示小午给的选择数量以及小枫每次需要陪伴的天数。 第二行输入 $n$ 个正整数 $a_i$ $(1\leq a_i \leq n-t+1)$ ，表示第 $i$ 个要求需要小枫从第 $a_i$ 天开始。 接下来 $n$ 行，每行两个整数 $cost_i,v_i$ $(0\leq cost_i,v_i\leq 10^5)$ ，分别表示陪伴小午需要花费的价格、无法满足小午的第 $i$ 个要求需要购买的礼物的价格。

输出一个整数表示小枫的最少花费。

输入 #1

6 2
5 5 1 2 3 4
3 9
8 3
2 5
1 8
8 9
4 2

输出 #1

C++ 编辑器

输入

输出