Camp Circular Bus

There are $N$ boarding and alighting stops in the camp, numbered from $1$ to $N$. On a clear morning, the driver starts the bus again to help soldiers move around the camp.

The driver's bus is called the camp circular bus and has the following features.

• The camp circular bus leaves stop $1$ at time $0$, visits stops $2$, $3$, $\cdots$, $N$ in order, then returns to stop $1$. It keeps repeating this route.
• After departure, the bus cannot stop until all $M$ soldiers have boarded and alighted.
• The bus has no capacity limit. A soldier who wants to board can always get on.

A soldier starts waiting for the bus at a time, boards the moment the bus reaches the boarding stop, and alights the moment the bus reaches the alighting stop.

The driver helped all $M$ soldiers move and finished work as soon as the last soldier alighted. Find the time when the driver finished work.

The first line contains the number of stops $N$ and the number of soldiers $M$, separated by a space. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000)$

The second line contains integers $t_i$, separated by spaces, which is the time to travel from stop $i$ to stop $i+1$. Here $t_N$ is the time to return from stop $N$ to stop $1$. $(1 \leq i \leq N;$ $1 \leq t_i \leq 1\,000)$

From the third line through line $2+M$, each line gives one soldier: the boarding stop $p_i$, the alighting stop $r_i$, and the time $c_i$ when the soldier started waiting for the bus at the boarding stop, separated by spaces. $(1 \leq i \leq M;$ $1 \leq p_i, r_i \leq N;$ $p_i \neq r_i;$ $0 \leq c_i \leq 10^9)$

Print one line with the time when the driver finished work.