보물 지도

보물 지도를 손에 넣었다. 지도는 금광 $n$개가 있는 곳으로 이어진다. 금광은 날마다 금을 내놓지만, 하루가 지날 때마다 그 양이 일정하게 줄어든다. 금광 $i$는 1일차에 $g_i$만큼 내놓고 하루에 $d_i$씩 줄어들므로, $k$일차에 금광 $i$에서 나오는 금의 양은 $\max(0,\ g_i - (k-1) \times d_i)$이다. 금광이 음수만큼 내놓는 일은 없다.

금광 사이에는 길이 있고, 길 하나를 건너는 데 며칠이 걸린다. 이동하는 동안에는 금을 얻지 못한다.

1일차에 1번 금광에 서 있고, 그날 1번 금광에서 나온 금을 전부 가져간다. 같은 금광에 이틀 연속 머무를 수 없으므로, 금을 챙긴 뒤에는 길을 따라 다른 금광으로 떠나야 한다. 이미 떠났던 금광으로 다시 돌아와도 되고, 돌아온 날에 그 금광에서 나오는 금을 다시 가져간다. 여행은 원하는 순간에 끝낼 수 있다.

가져갈 수 있는 금의 최대 총량을 구하라.

첫째 줄에 금광의 수 $n$과 길의 수 $m$이 주어진다. ($2 \le n \le 1000$, $1 \le m \le 1000$)

다음 $n$개 줄에 금광의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 1일차 산출량 $g$와 하루마다 줄어드는 양 $d$가 주어진다. ($1 \le g \le 1000$, $1 \le d \le 1000$) 예를 들어 $g = 9$, $d = 4$이면 1일차에 9, 2일차에 5, 3일차에 1이 나오고 4일차부터는 0이 나온다. 금광 번호는 입력에 나온 순서대로 1번부터 $n$번까지이고, 출발 지점은 1번 금광이다.

다음 $m$개 줄에 길의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 길이 잇는 두 금광의 번호 $a$, $b$와 그 길을 건너는 데 걸리는 일수 $t$가 주어진다. ($1 \le a < b \le n$, $1 \le t \le 100$) 길은 양방향이라 $a$에서 $b$로 갈 수도 있고 $b$에서 $a$로 갈 수도 있다.

가져갈 수 있는 금의 최대 총량을 정수 하나로 출력한다.