解题思路

这道题目需要我们在一个已经放置了若干物品的置物架上，找到放置新物品的最小移动成本。核心思路是检查所有可能的空隙和通过移动物品能创造的空隙，找到满足条件的最小移动次数。

具体步骤如下：

1. 检查现有空隙：首先遍历所有已存在物品之间的空隙，以及置物架两端的空隙，看是否有足够大的空间直接放置新物品。如果有，直接返回0。
2. 检查移动物品后的空隙：如果没有现成的足够大空隙，我们需要考虑移动连续的K个物品来创造空间。对于每个可能的连续K个物品的移动，计算移动后能获得的总空间（包括移动物品前后的空隙和物品之间的空隙），看是否能满足新物品的大小需求。
3. 寻找最小K：我们需要找到满足条件的最小K值。可以使用滑动窗口的方法来高效地检查所有可能的连续K个物品的移动情况。

题目内容

有一个长度为 $N$ 的置物架，上面一级放置着 $M$ 个物品，每个物品大小不同，占用了置物架不同大小的长度空间，且物品之间不一定连续放置，可能存在空隙。现在你想放置你自己的物品，且希望在保持物品原有顺序的情况下，尽可能不去移动置物架上已存在的物品，即你的策略是：

1.如果存在足够的长度空间能放置你的物品，则直接放置你的物品，此时移动的物品数量为 $0$ ;

2.或者，你可以选择从 $i$ 号物品开始的连续 $K$ 个物品，将它们紧密排列，以获得空间，此时移动物品的数量为 $K$ ，同时你将获得 $K$ 个物品中间的空隙，$i$ 号物品向前的空隙，以及 $i+k$ 号物品向后的空隙，这三个空隙1的总和空间。

给你指定的长度、物品的排列，和你需要放置的物品大小，计算移动的物品数量的最小值。

输入描述

输入格式

1.输入为 $M +1$ 行

2.第一行包含三个数字: $N$ $M$ $K$ 。其中 $N$ 为置物架长度，$M$ 为已经存在的物品数量，$K$ 为需要放置的物品大小

3.第二行开始，每一行描述一个已经在置物架上的物品。每一行包含两个数字 $Si$ $Ei$ 。其中 $Si$ 代表物品的起始位置，$Ei$ 代表物品的结束位置。用例保证输入的物品顺序是从小到大排序的。

输入约束

1.$0＜N＜=5*10^5$

2.$0＜M＜=10^5$

3.$0＜=Si＜Ei＜=5*10^5$ ，即物品一定具有长度，且不会超过置物架

4.所有数据均为整数，多个物品之间不会重叠，由输入保证

输出描述

输出数字，代表移动的物品数量的最小值

如果找不到放置的空间，输出 $-1$

样例1

输入

10 3 5
3 4
6 8
9 10

输出

1

说明

只需要把 $[3,4)$ 物品移动到最前，则新排布为 $[0,1)、[6,8)、[9,10)$，则在区间 $[1,6)$ 存在大小为 $5$ 的空隙，可放入新物品

样例2

输入

16 6 6
0 1
4 6
8 9
10 11
12 13
14 15

输出

2

说明

将位于 $[4,6)$ 位置的 $1$ 号物品 和 位于 $[8,9)$ 的 $2$ 号物品、和 $0$ 号物品紧密排列，则最新的物品排列如下图所示，可以获得大小为 $6$ 的空间，足够放置新的大小为 $5$ 的物品。

虽然移动 $[8,9)、[10,11)、[12,13)、[14,15)$ 四个物品也可以获得足够的空间，但是需要移动更多的物品