B. Ставки
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В Челябинске живет очень уважаемый бизнесмен Никита со странным прозвищем "БОСС". Как-то раз Никита решил съездить с его другом Алексеем на чемпионат мира по летнему биатлону. Никита, как особо важная персона, получил жетон, позволяющий ставить на каждом участке не более чем на одного спортсмена.

Для начала друзья узнали правила: в гонке n участков равной длины и m участников. Участники пронумерованы от 1 до m. Про каждого участника известно:

  • li — номер участка, с которого биатлонист начинает бежать,
  • ri — номер участка, на котором биатлонист заканчивает бежать,
  • ti — время, которое требуется биатлонисту чтобы преодолеть один участок пути,
  • ci — прибыль в рублях, которую получит поставивший на него человек, в случае победы i-ого спортсмена на одном из участков.

i-ый биатлонист проезжает участки с li по ri включительно. Весь путь участник пробегает за (ri - li + 1)·ti единиц времени. Одну секцию участник пробегает ровно за ti единиц времени. В случае победы спортсмена на k участках поставивший на него получит k·ci рублей.

На каждом участке победитель определяется независимо следующим образом: если есть хотя бы один биатлонист, бегущий данный участок, то из всех них победителем является тот, кто пробежал этот участок за минимальное время (преодолел участок за меньшее время, чем другие). В случае равенства времени побеждает спортсмен с меньшим порядковым номером. Если же участников этапа нет, то победитель на этом этапе неопределен. Стоит добавить, что в летнем биатлоне все участники движутся с постоянной скоростью.

Также стоит добавить, что Никита может ставить на каждом участке на любого участника, бегущего данный участок.

Помогите друзьям определить максимальную возможную прибыль.

Входные данные

В первой строке находится два целых числа n и m (1 ≤ n, m ≤ 100). Далее следуют m строк, в каждой из которых записано 4 целых числа li, ri, ti, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ti, ci ≤ 1000).

Выходные данные

Выведите одно целое число — максимальную прибыль в рублях, которую могут получить друзья. На каждом из n участков разрешается поставить деньги не более чем на одного спортсмена.

Примеры
Входные данные
4 4
1 4 20 5
1 3 21 10
3 3 4 30
3 4 4 20
Выходные данные
60
Входные данные
8 4
1 5 24 10
2 4 6 15
4 6 30 50
6 7 4 20
Выходные данные
105
Примечание

В первом тесте оптимально ставить: на 1-2 участках на 1 биатлониста, на 3 участке на 3 биатлониста, на 4 участке на 4 биатлониста. Итого: прибыль 5 рублей за 1 участок,прибыль 5 рублей за 2 участок, прибыль 30 рублей за 3 участок, прибыль 20 рублей за 4 участок. Суммарная прибыль 60 рублей.

Во втором тесте оптимально ставить: на 1 и 5 участках на 1 биатлониста, на 2-4 участке на 2 биатлониста, на 6-7 участках на 4 спортсмена. На 8 участке нет победителя. На 1 участке прибыль 10 рублей, на 2,3,4 по 15 рублей, на 5 участке прибыль 10 рублей, на 6,7 участках прибыль 20 рублей. Суммарная прибыль 105 рублей.