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

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

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

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

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

接下來(lái) 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⁵。