小藍(lán)是一所圖書館的管理員，圖書館中目前有 n 種書，第 i 種書有 a_i 本。

小藍(lán)目前有 m 條未來若干天中用戶的預(yù)約借閱記錄，每個(gè)借閱記錄由 b_i , l_i ,r_i 組成，表示在 l_i 日要借用一本書 b_i ，r_i 日歸還，r_i 日結(jié)束后圖書館才可以將這本書重新借出。

小藍(lán)分析了一下預(yù)約借閱記錄，發(fā)現(xiàn)現(xiàn)有的書不一定能滿足所有人的預(yù)約請(qǐng)求，于是小藍(lán)打算額外購買一些書加入到圖書館。小藍(lán)的預(yù)算有限，請(qǐng)問如果額外添加不超過 x 本書，最多有多少條預(yù)約記錄能得到滿足? 小藍(lán)可以選取一部分記錄使其滿足，不一定需要按借閱或預(yù)定的時(shí)間順序滿足。

輸入的第一行包含三個(gè)整數(shù) n, m, x ，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

第二行包含 n 個(gè)整數(shù) a₁, a₂, · · · , a_n，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔，表示目前擁有的每種書的本數(shù)。

接下來 m 行，每行包含 3 個(gè)整數(shù) b_i , l_i , r_i，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔，表示一條預(yù)約借閱記錄。

輸出一行包含一個(gè)整數(shù)表示給定條件下最多能滿足預(yù)約借閱的記錄數(shù)。

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

對(duì)于 10% 的評(píng)測(cè)用例，n, m ≤ 10 ，l_i ≤ r_i ≤ 10；

對(duì)于 50% 的評(píng)測(cè)用例，n, m ≤ 2000 ，l_i ≤ r_i ≤ 5000；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 100000 ，1 ≤ x ≤ m ≤ 200000 ，1 ≤ b_i ≤ n ， 1 ≤ l_i ≤ r_i ≤ 10⁶ ，0 ≤ a_i ≤ 10⁵。