Treasure Map

You have found a treasure map. It leads to $n$ gold mines. Each mine produces gold every day, but the daily haul shrinks by a fixed amount as the days pass. Mine $i$ produces $g_i$ on day 1 and loses $d_i$ per day, so on day $k$ mine $i$ produces $\max(0,\ g_i - (k-1) \times d_i)$. A mine never produces a negative amount.

Paths connect the mines, and crossing one path takes a whole number of days. You collect nothing while you travel.

On day 1 you stand at mine 1 and take all of that day's gold from it. You cannot stay at the same mine on two days in a row, so after collecting you have to leave along a path. You may come back to a mine you left earlier, and on the day you come back you take that mine's gold for that day again. You may end the trip at any moment.

Find the largest total amount of gold you can collect.

The first line contains the number of mines $n$ and the number of paths $m$. ($2 \le n \le 1000$, $1 \le m \le 1000$)

Each of the next $n$ lines describes one mine with its day 1 output $g$ and its daily decrease $d$. ($1 \le g \le 1000$, $1 \le d \le 1000$) For example, if $g = 9$ and $d = 4$, the mine produces 9 on day 1, 5 on day 2, 1 on day 3, and 0 from day 4 on. The mines are numbered 1 to $n$ in the order they appear in the input, and you start at mine 1.

Each of the next $m$ lines describes one path with the two mine numbers $a$ and $b$ it joins and the number of days $t$ needed to cross it. ($1 \le a < b \le n$, $1 \le t \le 100$) A path runs both ways, so it can be used from $a$ to $b$ and from $b$ to $a$.

Print the largest total amount of gold you can collect as a single integer.