Nanami likes playing games, and is also really good at it. This day she was playing a new game which involved operating a power plant. Nanami's job is to control the generators in the plant and produce maximum output. There are n generators in the plant. Each generator should be set to a generating level. Generating level is an integer (possibly zero or negative), the generating level of the i -th generator should be between l i and r i (both inclusive). The output of a generator can be calculated using a certain quadratic function f ( x ) , where x is the generating level of the generator. Each generator has its own function, the function of the i -th generator is denoted as f i ( x ) . However, there are m further restrictions to the generators. Let the generating level of the i -th generator be x i . Each restriction is of the form x u ≤ x v + d , where u and v are IDs of two different generators and d is an integer. Nanami found the game tedious but giving up is against her creed. So she decided to have a program written to calculate the answer for her (the maximum total output of generators). Somehow, this became your job. The first line contains two integers n and m (1 ≤ n ≤ 50; 0 ≤ m ≤ 100) — the number of generators and the number of restrictions. Then follow n lines, each line contains three integers a i , b i , and c i (| a i | ≤ 10; | b i |, | c i | ≤ 1000) — the coefficients of the function f i ( x ) . That is, f i ( x ) = a i x 2 + b i x + c i . Then follow another n lines, each line contains two integers l i and r i ( - 100 ≤ l i ≤ r i ≤ 100) . Then follow m lines, each line contains three integers u i , v i , and d i (1 ≤ u i , v i ≤ n ; u i ≠ v i ; | d i | ≤ 200) , describing a restriction. The i -th restriction is x u i ≤ x v i + d i . Print a single line containing a single integer — the maximum output of all the generators. It is guaranteed that there exists at least one valid configuration. In the first sample, f 1 ( x ) = x , f 2 ( x )