Thog is an avid TF2 (Thog's Fortnite 2) player, and he loves unlocking achievements in TF2; it was his love for TF2 that allowed him to discover alternate dimensions, as well as interdimensional portals to travel between them (the Nobel Prize was, unfortunately, not a TF2 achievement). To his delight, every dimension contains a different TF2!

When using a portal, Thog takes ~W_{Y_i}~ minutes to travel from dimension ~X_i~ to ~Y_i~ (note: the reversed connection from ~Y_i~ to ~X_i~ would take ~W_{X_i}~ minutes). Additionally, the TF2 in dimension ~i~ has ~A_i~ available achievements for Thog to receive, which he can only achieve once: the ~j^\text{th}~ achievement requires ~t_j~ minutes to complete and adds ~p_j~ points to Thog's global TF2 account.

Before Thog can start using his new technology, rival TF2 players sabotaged interdimensional travel, forcing Thog to spend at most ~D_i~ minutes in the ~i^\text{th}~ dimension. To make things worse, Thog's mom is coming home in ~H~ minutes, and she will force Thog to drop what he is doing and write his infamous Yahoo answer.

Help Thog find out the maximum amount of points while still starting and returning to his home (at the ~0^\text{th}~ dimension) within ~H~ minutes!

(Note: DMOJ and Thog are not affiliated with Fortnite.)

Input Specification

The first line will contain ~H~ ~(0 \le H \le 10\,000)~ and ~N~ ~(1 \le N \le 1\,000)~, the maximum number of minutes Thog can spend across all dimensions and the number of dimensions (which are labelled from ~0~ to ~N-1~).

The next ~N~ lines will contain ~D_i~ ~(0 \le D_i \le 100)~, ~A_i~ ~(0 \le A_i \le 100)~, and ~W_i~ ~(0 \le W_i \le 100)~, the maximum number of minutes Thog can spend in the ~(i-1)^\text{th}~ dimension, the number of achievements in the ~(i-1)^\text{th}~ dimension, and the number of minutes it takes to travel to the ~(i-1)^\text{th}~ dimension.

Before each next dimension line is printed, the next ~A_i~ lines directly after the ~i^\text{th}~ dimension will contain ~t_j~ ~(1 \le t_j \le D_i)~ and ~p_j~ ~(1 \le p_j \le 100)~, the number of minutes Thog needs to spend to acquire the ~j^\text{th}~ achievement option and the number of points received from completing the ~j^\text{th}~ achievement option.

The next ~N-1~ lines will contain ~X_i~ and ~Y_i~ ~(0 \le X_i < Y_i < N)~, a portal that allows Thog to travel between the ~{X_i}^\text{th}~ dimension and the ~{Y_i}^\text{th}~ dimension (0-indexed).

(Important note: the connections will always form a tree from the root dimension 0.)

Constraints

For all subtasks:

~1 \le N \le 1\,000~

~W_0 = 0~

Subtask 1 [20%]

~N = 1~

Subtask 2 [80%]

No additional constraints.

Output Specification

Output the maximum number of points Thog can achieve in ~H~ minutes (starting from his home at dimension 0).

Sample Input 1

50 1
70 4 0
20 7
35 5
15 10
4 6

Sample Output 1

23

Explanation for Sample Output 1

The maximum number of points Thog can achieve in 50 minutes is 23: he collects 7 points in 20 minutes, 10 points in 15 minutes, and 6 points in 4 minutes (the other achievement (5 points in 35 minutes) would push him over the maximum time he can spend in his initial dimension and the time he can spend collecting points).

Sample Input 2

100 2
80 4 0
20 10
70 40
80 50
30 20
70 2 1
40 10
20 40
0 1

Sample Output 2

80

Explanation for Sample Output 2

The maximum number of points Thog can achieve in 100 minutes is 80: he collects 40 points in 70 minutes, then he goes to dimension 1 in 1 minute and collects 40 points in 20 minutes, then he returns to his initial dimension in 0 minutes (which is the guaranteed travel time to his home in all test cases).

Sample Input 3

150 3
60 3 0
50 10
30 20
10 30
100 2 5
100 20
30 50
20 1 10
20 20
0 1
0 2

Sample Output 3

120

Explanation for Sample Output 3

The maximum number of points Thog can achieve in 150 minutes is 120: he collects 20 points in 30 minutes and 30 points in 10 minutes from his initial dimension, then he goes to dimension 1 in 5 minutes and collects 50 points in 30 minutes, then he goes to the dimension 2, taking 10 minutes (0 minutes to his home and 10 minutes to the third dimension), and collects 20 points in 20 minutes, then he returns home (from the third dimension) in 0 minutes.

Sample Input 4

100 5
60 3 0
50 10
30 20
40 30
100 2 5
100 20
30 50
20 1 10
20 20
50 2 10
10 50
50 10
100 1 5
50 10
0 1
0 2
1 3
3 4

Sample Output 4

130

Explanation for Sample Output 4

The maximum number of points Thog can achieve in 100 minutes is 130: he collects 30 points in 40 minutes from his initial dimension, then he goes to dimension 1 in 5 minutes and collects 50 points in 30 minutes, then he goes to the third dimension in 10 minutes and collects 50 points in 10 minutes, then he returns home in 5 minutes (back to dimension 1, then dimension 0).