Nhà máy sữa CodeMilk có ~N~ đại lý được xây dựng trên một con đường thẳng. Có thể mô tả con đường là một trục tọa độ, nhà máy sữa nằm tại vị trí gốc tọa độ, ~N~ đại lý ở tại các vị trí có tọa độ ~x_1,x_2,…,x_N~ ~(0 <x_1<x_2<⋯<x_N < 10^9)~, đại lý thứ ~i~ ~(i = 1,2,3,...,N)~ có vị trí tại tọa độ ~x_i~. Nhà máy có M chiếc xe dùng để vận chuyển sữa. Chiếc xe thứ ~i~, chuyển sữa từ đại lý ~s_i~ đến đại lý ~f_i~ ~(1 ≤s_i<f_i≤N)~, lượng xăng cần di chuyển cho ~1~ (đơn vị độ dài) là ~c_i~ (đơn vị thể tích) và số lần đổ xăng tối đa là ~r_i~, xe đi từ tọa độ ~x~ đến tọa độ ~y~ sẽ mất một lượng xăng ~|x-y|×c_i~. Các xe chỉ được di chuyển theo chiều dương của trục tọa độ và chỉ có thể đổ xăng khi đến vị trí của một đại lý nào đó. Xe không thể di chuyển nếu không còn xăng. Bình chứa xăng của ~M~ chiếc xe đều có dung tích giống nhau và bằng ~V~ (đơn vị thể tích). Khi bắt đầu xuất phát, bình xăng của tất cả các xe đã đầy xăng (không tính là một lần đổ xăng), mỗi lần đổ xăng, bình xăng được đổ đầy (tức là có ~V~ (đơn vị thể tích) xăng trong bình).</p>

Yêu cầu: Hãy tính xem, giá trị ~V~ nhỏ nhất bằng bao nhiêu để với mọi chiếc xe đều có thể vận chuyển được sữa, tức là chiếc xe thứ ~i~ có thể chuyển sữa được từ đại lý ~s_i~ đến đại lý ~f_i~ với mọi ~i=1,2,3,...,M~.

Input

• Dòng ~1~ ghi ~2~ số nguyên dương ~N~ và ~M~ tương ứng là số đại lý và số xe chở sữa.
• Dòng ~2~ ghi ~N~ số nguyên dương ~x_1,x_2,…,x_N~ ~(0<x_1<x_2<⋯<x_N<10^9)~ tương ứng là tọa độ của ~N~ đại lý.</li>
• ~M~ dòng cuối, dòng thứ ~i,(i=1,2,...,M)~ ghi ~4~ số nguyên ~s_i,f_i,c_i,r_i (1 ≤s_i<f_i≤N, 1 ≤c_i≤10^9;0≤r_i≤N)~ là thông tin của chiếc xe thứ i.</li>

Output

• Một số nguyên là giá trị nhỏ nhất của ~V~ để tất cả các xe đều có thể vận chuyển được sữa.

Subtask

• Có ~25\%~ số test ứng với ~1\le N \le 10^5, M = 1~.
• Có ~25\%~ số test ứng với ~2 \le N \le 100, 2 \le M \le 10~.
• ~50~ số test còn lại ứng với ~100 < N \le 400~, ~2 \le M \le 5.10^5~

Sample Input 1

5 2
1 3 8 12 15
1 3 10 0
2 4 5 1

Sample Output 1

70

Explanation 1

• Xe ~1~, di chuyển từ đại lý ~1~ đến đại lý ~3~, tức là tọa độ ~1~ đến tọa độ ~8~. Xe không được đổ xăng lần nào, do vậy sẽ dùng xăng trong bình lúc xuất phát. Lượng xăng ít nhất cần là ~|8-1|×10=70~ . Như vậy ~V~ bằng ~70~ thì xe ~1~ có thể đi được từ đại lý ~1~ đến đại lý ~3~.
• Xe ~2~, di chuyển từ đại lý ~2~ đến đại lý ~4~, tức là tọa độ ~3~ đến tọa độ ~12~. Xe được đổ xăng thêm một lần.
  • Đi từ tọa độ ~3~ đến tọa độ ~8~ hết ~|8-3|×5=25~.
  • Đi từ tọa độ ~8~ đến tọa độ ~12~ hết ~|12-8|×5=20~.
  • Như vậy, ~V = 25~ thì xe thứ ~2~ đi từ đại lý ~2~ đến đại lý ~3~; đổ xăng tại đại lý ~3~ và đi từ đại lý ~3~ đến đại lý ~4~.

• Do vậy, giá trị ~V~ nhỏ nhất để ~2~ xe có thể vận chuyển được sữa là ~70~.