Gruszki są bogate w witaminy i można powiedzieć, że są bardzo zdrowym owocem.

Jak to możliwe, że słynny detektyw Conan Edogawa pozostaje wiecznie młody, mimo że wszędzie, gdzie się pojawi, ktoś traci życie? Sekret tkwi w tym, że codziennie pije zupę z gruszek i jagód goji. Jednak dostawca, który od dawna zaopatrywał go w gruszki, niestety zmarł, więc Conan musi zadowolić się kupowaniem gruszek w detalu u ulicznych sprzedawców.

Conan Edogawa musi zaplanować zaopatrzenie w gruszki na kolejne $n$ dni. W dniu $i$ potrzebuje $a_i$ gruszek, aby dbać o swoje zdrowie.

Podczas swoich podróży detektywistycznych Conan spotka $m$ sprzedawców. $i$-tego sprzedawcę spotyka w dniu $t_i$. Sprzedawca ten może sprzedać łącznie $b_i$ gruszek w cenie jednostkowej $c_i$, które jednak nie są zbyt świeże i psują się po $k_i$ dniach. Oznacza to, że jeśli Conan je kupi, może je spożyć tylko w dniach od $t_i$ do $t_i + k_i - 1$.

Zaplanuj zakupy Conana tak, aby zminimalizować całkowity koszt.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite dodatnie $n$ oraz $m$, oznaczające odpowiednio liczbę dni i liczbę sprzedawców.

W drugiej linii znajduje się $n$ liczb całkowitych dodatnich $a_i$.

W kolejnych $m$ liniach znajdują się po cztery liczby całkowite $b_i, c_i, t_i, k_i$, oznaczające odpowiednio limit sprzedaży, cenę jednostkową, dzień spotkania oraz okres świeżości.

Wyjście

Jeśli zaplanowanie zakupów jest możliwe, wypisz minimalny koszt.

Jeśli nie ma rozwiązania, wypisz $-1$.

Przykład

Wejście 1

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

Wyjście 1

38

Ograniczenia

$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$

Podzadanie 1 (45 pkt.): $1 \le n \le 50, 1 \le m \le 100$

Podzadanie 2 (55 pkt.): $1 \le n \le 1000, 1 \le m \le 2000$