Portals
You are standing at the first index of an array of length . At index , you can either take a step forward to , or if there is a portal ( portals) such that , you can teleport to index . The score of a path is defined as the sum of values of the indicies you visit. What is the maximum score with which you can get from index to index ?
Input Format
The first line is two integers n m
, the number of numbers and portals.
The next line is n
integers, the array.
The next m
lines are each three integers x y z
, the portals.
Sample Input
5 1
1 2 -100 4 5
1 1 3
Sample Output
12
Constraints
Comments