题目描述

小明跟他的小朋友们共 $n$ 人商量在保证作业做完的前提下出去玩。第 $i$ 个小朋友可以玩耍的时间段是 $S_i \sim T_i$。这里 $S_i \sim T_i$ 表示的是时间区间，比如 $S_i=2,T_i=4$，意味着这位小朋友在时刻 $1$ 不能玩，时刻 $2,3,4$ 可以去玩，时刻 $4$ 以后都不能出去玩。如果在某个时刻，在一起玩的小朋友个数不少于 $k$ 个，那么这一时刻就是幸福的。现在要求出小朋友共有多少个时刻是幸福的。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示小朋友个数和幸福时刻所需的最小人数。 第二行包含 $n$ 个整数 $S_1, S_2, \ldots, S_n$，分别表示每个小朋友可以开始玩耍的时刻。 第三行包含 $n$ 个整数 $T_1, T_2, \ldots, T_n$，分别表示每个小朋友玩耍的结束时刻。

输出格式

输出一行一个整数，表示幸福时刻的总数。

样例

4 3
1 2 2 4
5 2 4 6

2

提示

四个小朋友的时间段分别为 $[1,5]$, $[2,2]$, $[2,4]$, $[4,6]$。

• 时刻 $2$：小朋友 $1,2,3$ 同时在玩，人数 $3 \ge k$，幸福；
• 时刻 $3$：只有小朋友 $1,3$，人数不足；
• 时刻 $4$：小朋友 $1,3,4$ 同在，人数 $3 \ge k$，幸福； 因此幸福时刻为 $2$ 和 $4$，共 $2$ 个。

数据范围

• 对于 $50\%$ 的数据：$n \le 1000$，$1 \le S_i \le T_i \le 1000$
• 对于 $100\%$ 的数据：$n \le 100000$，$1 \le S_i \le T_i \le 10^9$，$1 \le k \le n$