F. Traffic Lights
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A new school year has begun, which means you'll have to ride the bus through traffic jams to the university again.

You know that there are n intersections with traffic lights between the starting and ending stops.

The starting stop is located immediately after intersection 0, and the ending stop is just after intersection n.

You know that the bus takes ai seconds to travel from the (i - 1)-th intersection to the i-th intersection. The time spent at stops can be neglected.

For the traffic light at the i-th intersection, three characteristics are known:

  • ri — how many seconds the red light is on at the traffic light;
  • gi — how many seconds the green light is on;
  • di — how many seconds before your bus boarding the green light turned on at the traffic light.

If the bus arrives exactly when the light switches to red, it will not be able to pass.

Using all this information, determine how many seconds the entire bus trip will take from start to finish.

Input

The first line contains an integer n (1 ≤ n ≤ 104) — the number of intersections on your way.

The second line contains integers a1, a2, ..., an (1 ≤ ai ≤ 104,  i = 1, 2, ..., n) — the time it takes for the bus to travel from the (i - 1)-th to the i-th intersection.

Each of the following n lines contains three integers ri, gi, di (1 ≤ ri, gi ≤ 1000, 1 ≤ di ≤ 104) — the characteristics of the i-th traffic light.

Output

In a single line, output an integer — the time it will take for you to travel by bus from the starting stop to the ending stop.

Example
Input
3
100 110 50
80 20 50
60 10 100
30 40 50
Output
370
Note

First test example

  • You reached the 1-st traffic light in 100 seconds.
  • The 1-st traffic light is green during the time intervals [ - 50; - 30], [50;70]; [150;170];
  • You arrived during the red light, so the bus will wait until 150 seconds.
  • The bus will reach the 2-nd traffic light in 110 seconds — it has already been 150 + 110 = 260 seconds.
  • The 2-nd traffic light is green during the time intervals [ - 100; - 90], ... [180;190]; [250;260]; [320;330].
  • The bus arrived exactly at the beginning of the red light, so it will have to wait until 320 seconds.
  • The bus will reach the 3-rd traffic light in 50 seconds — it has already been 320 + 50 = 370 seconds.
  • The 3-rd traffic light is green during the time intervals [ - 50; - 10], ... [300;340]; [370;410].
  • The bus arrived exactly at the beginning of the green light, so it passed the intersection immediately without waiting.
  • In total, you traveled the entire distance in 370 seconds.