图书借阅 ### 问题描述 小蓝是一所图书馆的管理员, 图书馆中目前有 $n$ 种书, 第 $i$ 种书有 $a_{i}$ 本。 小蓝目前有 $m$ 条末来若干天中用户的预约借阅记录, 每个借阅记录由 $b_{i}, l_{i}, r_{i}$ 组成, 表示在 $l_{i}$ 日要借用一本书 $b_{i}, r_{i}$ 日归还, $r_{i}$ 日结束后图书馆才可 以将这本书重新借出。 小蓝分析了一下预约借阅记录, 发现现有的书不一定能满足所有人的预约 请求, 于是小蓝打算额外购买一些书加入到图书馆。小蓝的预算有限, 请问如 果额外添加不超过 $x$ 本书, 最多有多少条预约记录能得到满足? 小蓝可以选取 一部分记录使其满足, 不一定需要按借阅或预定的时间顺序满足。 ### 输入格式 输入的第一行包含三个整数 $n, m, x$ ，相邻两个整数之间用一个空格分隔。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$, 相邻两个整数之间用一个空格分隔, 表 示目前拥有的每种书的本数。 接下来 $m$ 行, 每行包含 3 个整数 $b_{i}, l_{i}, r_{i}$, 相邻两个整数之间用一个空格分 隔, 表示一条预约借阅记录。 ### 输出格式 输出一行包含一个整数表示给定条件下最多能满足预约借阅的记录数。 ### 样例输入 ```text 3 11 3 1 0 2 1 2 4 1 1 2 1 4 5 1 3 5 1 1 3 2 1 1 2 2 2 2 3 3 2 1 2 2 3 4 3 1 5 ``` ### 样例输出 ```text 10 ``` ### 评测用例规模与约定 对于 $10 \\%$ 的评测用例, $n, m \leq 10, l_{i} \leq r_{i} \leq 10$; 对于 $50 \\%$ 的评测用例, $n, m \leq 2000, l_{i} \leq r_{i} \leq 5000$; 对于所有评测用例, $1 \leq n \leq 100000,1 \leq x \leq m \leq 200000,1 \leq b_{i} \leq n$, $1 \leq l_{i} \leq r_{i} \leq 10^{6}, 0 \leq a_{i} \leq 10^{5}$ 。