高桥老弟喜欢一遍又一遍的看同一部电影。每看一遍就会获得一定的幸福感

但是高桥老弟十分健忘，所以他一旦看到另一部电影，就会忘记之前看过的电影，所以当他再看一次之前看过的那个电影时，他又会得到第一次观看时的幸福感

当高桥老弟连续观看同一部电影第i次时获得的幸福感为Hi，因此连续k次观看同一部电影获得的幸福感就是H1+H2+…+Hk

现给出高桥老弟连续观看同一部电影第i次获得的幸福感Hi和当日的电影时间表，请求出高桥老弟最多能获得多少幸福感

注意

• 你不能从电影的中间开始观看或看到一半离场
• 如果一个电影的开始时间恰为另一部电影的结束时间，你仍可以同时观看这两部电影

输入格式

第一行为一个整数N表示当日的电影场次数(1<=N<=3000).

第二行为N个整数，第i个整数表示高桥老弟连续第i次观看同一部电影时获得的幸福感Hi(1<=Hi<=10000).

保证当i<j时，Hi<Hj.

从第三行到第N+2行，第i+2行(1<=i<=N)有三个整数分别表示电影的编号(同一标号为同一部电影)、电影开始的时间、电影结束的时间(保证电影开始的时间早于电影结束的时间，且都小于100000).

输出格式

一行，高桥老弟最多能获得的幸福感.

说明/提示

样例1

高桥老弟连续观看两场标号为1的电影获得总幸福感为100+200=300.