题目描述

你计划通过订阅《每周打造邪恶机器人》，收集零件并组装机器人，最终征服世界。

一台完整的邪恶机器人需要各使用一个零件 $1,2,\ldots,N$，共 $N$ 种零件。

订阅服务持续 $M$ 周。第 $i$ 周会分别送来一个零件：

也就是说，第 $i$ 周会收到区间 $[L_i,R_i]$ 中每种零件各一个。

零件 $i$ 的重量为 $w_i$。你的基地最多只能承受总重量 $K$，因此任意时刻，尚未用于组装的零件总重量都不能超过 $K$。

你不能拒收当周送来的零件。为了确保新零件能够被接收，你只能在零件送达之前，秘密丢弃手中已有的若干零件。

整个过程如下：

• 初始时没有任何零件。
• 对 $i=1,2,\ldots,M$，依次执行：
  1. 丢弃当前持有的零个或多个零件；
  2. 获得零件 $L_i,L_i+1,\ldots,R_i$ 各一个；此时所有尚未组装的零件总重量必须不超过 $K$；
  3. 可以执行零次或多次组装操作。每次组装消耗零件 $1,2,\ldots,N$ 各一个，并得到一台邪恶机器人。

你可以适当地选择每周送货前丢弃哪些零件。在始终满足重量限制的前提下，求最多能够组装多少台邪恶机器人。

题目保证，在给定约束下，总能通过某种丢弃方式使每次收货后的零件总重量不超过 $K$。

输入格式

输入包含多组测试数据。

每组测试数据格式如下：

N M K
w1 w2 ... wN
L1 R1
...
LM RM

• 第一行输入三个整数 $N,M,K$，分别表示零件种类数、送货周数和基地耐重上限；
• 第二行输入 $N$ 个整数 $w_1,w_2,\ldots,w_N$，表示各类零件的重量；
• 接下来 $M$ 行，第 $i$ 行输入两个整数 $L_i,R_i$，描述第 $i$ 周收到的零件区间。

输入以一行三个整数 0 0 0 结束。

输出格式

对于每组测试数据，输出一行一个整数，表示最多能够组装的邪恶机器人数量。

数据范围

保证：

所有测试数据中 $N$ 的总和不超过 $2\times 10^5$，$M$ 的总和不超过 $2\times 10^5$。

样例

6 6 30
3 1 4 1 5 9
6 6
3 5
5 6
1 3
1 4
3 4
6 6 30
3 1 4 1 5 9
3 5
5 6
1 3
1 4
3 4
6 6
2 4 9
1 8
1 1
1 1
2 2
2 2
8 9 183
20 17 20 15 19 17 19 19
5 6
1 4
6 8
7 7
5 8
1 2
1 5
3 8
3 4
0 0 0

1
2
1
3