Груши богаты витаминами, поэтому их можно назвать очень полезным для здоровья фруктом.

Как знаменитому детективу Эдогаве Конану удается сохранять вечную молодость, несмотря на то, что везде, где он появляется, кто-то лишается жизни? Секрет в том, что каждый день он пьет суп из груш и ягод годжи. Однако поставщик, который долгое время поставлял ему груши оптом, к сожалению, скончался, и теперь ему приходится покупать груши в розницу у уличных торговцев.

Эдогаве Конану нужно спланировать поставки груш на ближайшие $n$ дней. В $i$-й день ему требуется $a_i$ груш для поддержания здоровья.

Во время своих расследований Конан встречает $m$ торговцев. $i$-й торговец встречается в день $t_i$, он может продать в общей сложности $b_i$ груш по цене $c_i$ за штуку. Поскольку груши могут быть не первой свежести, они портятся через $k_i$ дней. Это означает, что если Конан купит их, он сможет употребить их только в период с $t_i$ по $t_i + k_i - 1$ день включительно.

Пожалуйста, спланируйте его покупки так, чтобы минимизировать общие затраты.

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

Первая строка содержит два целых положительных числа $n$ и $m$, обозначающие количество дней и количество торговцев.

Вторая строка содержит $n$ целых положительных чисел $a_i$.

Далее следуют $m$ строк, каждая из которых содержит четыре целых числа $b_i, c_i, t_i, k_i$, обозначающие соответственно максимальное количество груш для продажи, цену за одну грушу, день встречи и срок годности.

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

Если план покупок возможен, выведите минимальную стоимость.

Если решения не существует, выведите $-1$.

Примеры

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

3 3
3 5 4
6 1 1 3
3 10 1 2
4 3 2 2

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

38

Ограничения

$1 \le n \le 1000$, $1 \le m \le 2000$, $1 \le a_i, b_i, c_i \le 1000$, $1 \le t_i, k_i, t_i + k_i - 1 \le n$

Подзадача 1 (45 баллов): $1 \le n \le 50, 1 \le m \le 100$

Подзадача 2 (55 баллов): $1 \le n \le 1000, 1 \le m \le 2000$