猪猪养成计划2
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}Tobo 养了 n 只猪猪，但是 Tobo 为了不让它们吃醋，所以一视同仁不管陪哪只猪猪都只陪 m 天。
\hspace{15pt}现在第i只猪猪有个要求，要 Tobo 第 a_i 天去陪它，即需要从第 a_i 天陪到第 a_i+m-1 天。然而，因为 Tobo 精力有限，一天只能陪一只猪猪，显然 Tobo 大概率不能陪伴他的每只猪猪。
\hspace{15pt}如果不陪第 i 只猪猪，就要给它买 val_i 价值的礼物来补偿它；反之，如果陪它，就要花费 b_i 的精力。
\hspace{15pt}现在 Tobo 需要做一个抉择来选择陪的猪猪来使得花费的金钱与精力之和最少。他想知道这个最小值是多少。

输入描述:

\hspace{15pt}第一行输入两个整数 n, m \left(1 \leq m \leq n \leq 10^5\right) 代表猪猪数量、陪伴猪猪的天数。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(1 \leq a_i \leq n-m+1\right) 代表第 i 只猪猪需要你第 a_i 天去陪它。
\hspace{15pt}此后 n 行，每行输入两个整数 b_i, val_i \left(0 \leq b_i, val_i \leq 10^5\right) 代表陪第 i 只猪猪需要花费的精力、不陪伴第 i 只猪猪需要花费的金钱。

输出描述:

\hspace{15pt}在一行上输出一个整数，表示 Tobo 最少需要花费的金钱与精力之和。
示例1

输入

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

输出

复制 
23

说明

\hspace{15pt}在这个样例中，我们可以证明，只陪伴第一、四只猪猪是最优的；其余四只猪猪需要花费金钱购买礼物。
示例2

输入

复制 
15 4
4 10 4 10 1 3 2 3 1 7 12 4 8 7 7
5 4
5 6
9 0
2 8
5 5
4 1
8 4
7 0
5 2
5 8
8 4
8 0
0 0
3 1
6 7

输出

复制 
44