Dadas operates prism mines and wants to build mining modules.
Module has candidate designs. Exactly one design must be selected for each module. Design gives module performance and consumes prisms per hour. Every module must be built. Its consumption is counted once, regardless of how many mines use it, including when no mine uses it.
Mine uses two distinct modules . Let be the index of the design selected for module . This mine produces prisms per hour. A module may be used by several mines simultaneously. Several mines may use the same pair of modules; the production of every mine is counted separately.
The hourly net profit is the total production of all mines minus the total consumption of all modules. Find the maximum possible hourly net profit.
The input is given from Standard Input in the following format:
Print the maximum hourly net profit. The answer may be negative.
The first line gives the number of mines and the number of modules . The next lines give the number of candidate designs for each module, followed by each design's performance and consumption. The final lines give the two module indices used by each mine. Candidate designs are not necessarily sorted by performance.
| 3 | 55 | No additional constraints. |