CF434D Nanami's Power Plant

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}

The first line contains two integers $ n $ and $ m (1

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)=x+1 $ , and $ f_{3}(x)=x+2 $ , so we are to maximize the sum of the generating levels. The restrictions are $ x_{1}