P17877 糖葫芦 / tanghulu

糖葫芦是老北京最具代表性的传统特色小吃之一，酸甜晶莹，常伴随在冬日热闹的庙会与胡同街巷之中。 制作地道的北京糖葫芦，关键在于“熬糖”与“挂糖”。先将洗净去核的山楂串在竹签上；随后将白砂糖加水熬煮至起泡变稠、泛出清亮的焦黄色。待糖浆火候恰到好处，便要将整串山楂迅速浸入滚烫浓稠的糖浆中轻转一圈，使其均匀裹上一层薄糖，随即取出摊晾冷却，凝结出薄脆透亮的糖壳。

小 M 打算学着制作一些糖葫芦。他已经串好了水果串，熬好了糖浆，接下来需要进行挂糖的步骤。 小 M 准备了 $n$ 锅糖浆，第 $i$（$1 \le i \le n$）锅初始有 $a_i$ 单位糖浆。制作一串长度为 $l$ 的糖葫芦时，需要选择一锅当前剩余量不少于 $l$ 的糖浆将其浸没；制作完成后，该锅糖浆的剩余量减少 $1$ 单位（若剩余量减为 $0$，该锅糖浆被移除）。 小 M 需要按照编号从小到大的顺序制作 $m$ 批糖葫芦，第 $i$（$1\le i\le m$）批有 $c_i$ 串，每串长度均为 $b_i$。糖葫芦需要逐串制作，只有在第 $i$ 批的糖葫芦全部制作完成后，才能开始制作第 $i+1$ 批。制作每一串糖葫芦时，小 M 均可以从当前所有糖浆锅中独立选择。 在开始制作前，以及制作任意一串糖葫芦的前后，小 M 都可以进行任意次合并操作。合并操作有一个给定的损耗常数 $k$，每次合并会固定损耗 $k$ 单位糖浆。每次合并时，小 M 需要选择两锅当前剩余量分别为 $x,y$ 且满足 $x+y>k$ 的糖浆，将它们合并为一锅剩余量为 $x+y-k$ 的新糖浆，并移除原来的两锅。 合并糖浆会带来损耗，因此小 M 希望尽可能少地进行合并。请你求出完成所有糖葫芦制作所需的最少合并次数，或报告无论如何都无法完成制作。

**本题包含多组测试数据。** 输入的第一行包含两个整数 $c,t$，分别表示测试点编号与测试数据组数。特别地，若 $c=0$，则该测试点为样例。 接下来依次输入 $t$ 组测试数据。对于每组测试数据： - 第一行包含三个正整数 $n,m,k$，分别表示初始糖浆锅数、糖葫芦批数和每次合并损耗的糖浆量。 - 第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示各锅糖浆的初始量。 - 接下来 $m$ 行，第 $i$ 行包含两个正整数 $b_i,c_i$，分别表示制作第 $i$ 批中的每串糖葫芦所需的最低糖浆剩余量，以及这一批的串数。

对于每组测试数据，输出一行，包含一个整数，表示所需的最少合并次数。若无法完成全部制作，输出 $-1$。

**【样例 1 解释】** 对于第一组测试数据，一种合法方案如下： - 第一批，使用初始量为 $5$ 的那锅糖浆制作两串糖葫芦，其剩余量变为 $3$。 - 第二批，使用初始量为 $8$ 的那锅糖浆制作两串糖葫芦，其剩余量变为 $6$。 此时，各锅糖浆的剩余量为 $2,3,3,3,6$。 第三批按以下顺序操作： 1. 合并剩余量为 $6,3$ 的两锅糖浆，得到 $7$ 单位糖浆。 2. 合并剩余量为 $7,3$ 的两锅糖浆，得到 $8$ 单位糖浆。 3. 使用这锅糖浆制作一串糖葫芦，其剩余量变为 $7$。 4. 合并剩余量为 $7,3$ 的两锅糖浆，得到 $8$ 单位糖浆。 5. 使用这锅糖浆制作最后一串糖葫芦。 共进行 $3$ 次合并。可以证明，不存在合并次数少于 $3$ 的合法方案。 对于第二组测试数据，唯一的一锅糖浆在制作两串糖葫芦后，剩余量变为 $1$，无法制作第三串，也无法进行合并。 对于第三组测试数据，第一批使用两锅糖浆各制作一串，制作后两锅均剩余 $2$ 单位糖浆；第二批再使用两锅各制作一串，即可完成全部制作，无需进行合并。 **【样例 2】** 见题目目录下的 `tanghulu/tanghulu2.in` 与 `tanghulu/tanghulu2.ans`。 该样例满足测试点 $1,2$ 的约束条件。 **【样例 3】** 见题目目录下的 `tanghulu/tanghulu3.in` 与 `tanghulu/tanghulu3.ans`。 该样例满足测试点 $3,4$ 的约束条件。 **【样例 4】** 见题目目录下的 `tanghulu/tanghulu4.in` 与 `tanghulu/tanghulu4.ans`。 该样例满足测试点 $5\sim 7$ 的约束条件。 **【样例 5】** 见题目目录下的 `tanghulu/tanghulu5.in` 与 `tanghulu/tanghulu5.ans`。 该样例满足测试点 $8\sim 10$ 的约束条件。 **【样例 6】** 见题目目录下的 `tanghulu/tanghulu6.in` 与 `tanghulu/tanghulu6.ans`。 该样例满足测试点 $11\sim 13$ 的约束条件。 **【样例 7】** 见题目目录下的 `tanghulu/tanghulu7.in` 与 `tanghulu/tanghulu7.ans`。 该样例满足测试点 $16$ 的约束条件。 **【数据范围】** 设 $N$ 为单个测试点内所有测试数据的 $n$ 的和，$M$ 为单个测试点内所有测试数据的 $m$ 的和。对于所有测试数据，均有： - $0\le c\le 20$，$1\le t\le 10^3$； - $1\le n,m\le 10^5$，$N,M\le 5\times 10^5$； - $1\le k\le 10^{13}$； - 对于所有 $1\le i\le n$，均有 $1\le a_i\le 10^{13}$； - 对于所有 $1\le i\le m$，均有 $1\le b_i,c_i\le 10^{18}$。 各测试点的具体限制如下表所示。 ::cute-table{tuack} |测试点编号|$n\le$|$N\le$|$m\le$|$M\le$|特殊性质| |:----:|:----:|:----:|:----:|:----:|:----:| |$1,2$|$5$|$50$|$5$|$50$|A| |$3,4$|$1$|$10^3$|$10^5$|$5\times10^5$|无| |$5\sim7$|$10^5$|$2\times10^5$|^|$2\times10^5$|B| |$8\sim10$|^|^|$1$|$10^3$|无| |$11\sim13$|^|^|$2$|$2\,000$|^| |$14,15$|^|^|$100$|$10^5$|^| |$16$|^|^|$10^5$|$2\times10^5$|A| |$17,18$|^|^|^|^|无| |$19,20$|^|$5\times10^5$|^|$5\times10^5$|^| 特殊性质 A：对于所有 $1\le i\le m$，均有 $c_i=1$。 特殊性质 B：对于所有 $1\le i\le m$，均有 $b_i>\max_{1\le j\le n}a_j$。