P. Dungeon
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Free to play, pay to win!
—Anonymous

A knight of level 0 in the dungeon is in trouble! The dungeon can be abstracted as a long path of length $$$D$$$, with the knight initially at position 0. There are two possible events happening in the dungeon:

  1. If he encounters a monster with health $$$h$$$ and his current level is less than $$$h$$$, he has to pay some coins to beat the monster.
  2. If he encounters a shop that sells magic potions that could increase him to level $$$l$$$, he could pay some coins to buy it. However, he won't be able to use the potion if he is already higher than level $$$l$$$.

As a knight, he can never retreat on his way. There are $$$n$$$ monsters and $$$m$$$ shops on his way, the $$$i$$$-th monster is at position $$$a_i$$$, has health $$$h_i$$$, and he needs to pass using $$$f_i$$$ coins if he can't beat it. The $$$i$$$-th shop is at position $$$b_i$$$, sells potions that are able to increase his health level to $$$l_i$$$, and he will need $$$w_i$$$ coins to buy the potion.

What's the minimum money he needs to go through the dungeon?

Input

The first line contains 3 integers $$$D,n,m$$$ $$$(1\le D\le 10^9,1\le n,m\le 10^5)$$$.

The next $$$n$$$ lines each contains 3 integers $$$a_i,h_i,f_i$$$ $$$(1\le a_i\le D,1\le h_i,f_i\le 10^9)$$$.

The next $$$n$$$ lines each contains 3 integers $$$b_i,l_i,w_i$$$ $$$(1\le b_i\le D,1\le l_i,w_i\le 10^9)$$$.

All locations of monsters and shops are distinct.

Output

The minimum number of coins he needs to go through the dungeon.

Examples
Input
10 4 3
1 6 30
3 2 50
5 6 100
8 30 1000
2 5 10
6 30 100
7 30 50
Output
190
Input
8 4 3
2 5 100
4 3 100
5 1 100
7 7 15
1 3 0
6 9 100
8 1 50
Output
115
Note

In the first example, one optimal solution is as follows:

At the first monster, he pays $$$30$$$ coins to pass.

At the first shop, he buys the magic potion with $$$10$$$ coins.

He can beat the second monster with his current health level $$$5$$$.

At the third monster, he pays $$$100$$$ coins to pass.

At the second shop, he buys nothing.

At the third shop, he buys the magic potion with $$$50$$$ coins, recovering to health level $$$30$$$.

He can beat the last monster easily.

The total cost is $$$30 + 10 + 100 + 50=190$$$.