Problem D. Easy money ≡

Statement

Young programmer Vasya was not at all interested in car races, but many of his friends were. One day, friends persuaded Vasya to come with them to a sports bar to drink beer and watch some very important race involving N cars — they told Vasya the name of the race, but he immediately forgot it.

At first Vasya was not keen to go, but the perspective of a good beer won him over.

After an hour at the bar, Vasya understood that that the endless images of the cars driving around and around were just as boring with beer as without it. His friends, however, got quite excited and started to place bets on race results. Due to the amount of beer consumed, the bets were wild and some of them did not reflect actual chances at all. In total, M bets were suggested.

Since Vasya was unable to have fun, he decided at least to make some profit. All bets are of the form "I bet A roubles versus B roubles that car p will come ahead of car q". That means betting person agrees to pay A roubles if he was wrong (i.e. q will come ahead of car p), and requires the other side to pay him B roubles if he was right.

By betting on the same cars with different friends, Vasya would in some cases guarantee himself a net win, even if he loses some of the bets. So as not to alienate too many of his friends, Vasya decided to accept only two bets.

Find two bets for Vasya which will guarantee him the largest profit in the worst case.

Input file format

Input file contains integers N M followed by M bet descriptions.

Each bet description contains integers A_i B_i p_i q_i.

Output file format

Output file must contain a single integer — the maximum amount of guaranteed profit. If there is no way to select two bets to be always profitable, output must contain 0.

Constraints

2 ≤ N, M ≤ 10000;

1 ≤ A_i, B_i ≤ 10000;

1 ≤ p_i, q_i ≤ N, p_i ≠ q_i;

Sample tests

2 2
100 10 1 2
100 10 2 1

90

3 3
200 100 1 2
40 50 2 1
100 1 1 3

0