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

小蓝是一所图书馆的管理员，图书馆中目前有 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⁵。