蓝桥杯2022年第十三届决赛真题-图书借阅（Java组）

小蓝是一所图书馆的管理员，图书馆中目前有 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₁, a₂, · · · , a_n，相邻两个整数之间用一个空格分隔，表示目前拥有的每种书的本数。

接下来 m 行，每行包含 3 个整数 b_i , l_i , r_i，相邻两个整数之间用一个空格分隔，表示一条预约借阅记录。

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

10

对于 10% 的评测用例，n, m ≤ 10 ，l_i ≤ r_i ≤ 10；

对于 50% 的评测用例，n, m ≤ 2000 ，l_i ≤ r_i ≤ 5000；

对于所有评测用例，1 ≤ n ≤ 100000 ，1 ≤ x ≤ m ≤ 200000 ，1 ≤ b_i ≤ n ， 1 ≤ l_i ≤ r_i ≤ 10⁶ ，0 ≤ a_i ≤ 10⁵。