Cho dãy ~n~ số nguyên ~a_1, a_2, …, a_n~ và một số nguyên ~k~. Mức độ đẹp của một dãy con liên tiếp ~a_i, a_{i+1}, …, a_j~ được đánh giá bằng ~GCD(a_i, a_{i+1}, …, a_j).(a_i + a_{i+1} + … + a_j)~, tức là độ đẹp bằng ước chung lớn nhất của các phần tử trong dãy con nhân với tổng các phần tử trong dãy con đó.

Yêu cầu: Tìm dãy con liên tiếp có ít nhất ~k~ phần tử và có mức độ đẹp là lớn nhất.

Input

• Dòng 1: Hai số nguyên ~n, k\ (1 ≤ k ≤ n ≤ 10^6)~;
• Dòng 2: ~n~ số nguyên ~a_1, a_2, …, a_n\ (1 ≤ a_i ≤ 10^6)~.

Output

• Ghi ra một số nguyên duy nhất là mức độ đẹp tìm được.

Subtask

• 10% số điểm tương ứng với 10% số test có ~n, k ≤ 100~;
• 20% số điểm tương ứng với 20% số test có ~n, k ≤ 5000~;
• 25% số điểm tương ứng với 25% số test có ~a_i ≤ 100~;
• 20% số điểm tương ứng với 20% số test có ~n, k ≤ 5.10^4~;
• 25% số điểm tương ứng với 25% số test không có ràng buộc gì thêm

Example

Sample Input

6 2
4 4 4 3 1 3

Sample Output

48

Trong dịp lễ giáng sinh, siêu thị ~ABC~ có chính sách giảm giá ~n~ mặt hàng. Các mặt hàng được trưng bày theo thứ tự từ trái qua phải với mức giá ưu đãi là ~p_i~, với số lượng không giới hạn với mỗi loại mặt hàng. Có ~m~ khách hàng thân thiết vô cùng yêu thích chương trình giảm giá này, người thứ ~i~ mang tới số tiền là ~t_i~ và sẽ đi từ vị trí ~l_i~ tới vị trí ~r_i~. Tại mỗi vị trí, người này sẽ cố gắng mua nhiều nhất số hàng có thể tới khi không còn đủ tiền mua.

Yêu cầu: Hãy xác định số tiền còn lại của từng người sau khi mua hàng.

Input

• Dòng đầu tiên chứa số nguyên dương ~n, m~
• Dòng thứ hai chứa ~n~ số, số thứ ~i~ là ~p_i~ mô tả giá tiền của mặt hàng thứ ~i~
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~t_i,l_i,r_i~ xác định số tiền và khoảng cách di chuyển của người thứ ~i~.

Constraints

• ~1 \le n,m \le 2*10^5~
• ~1 \le p_i,t_i \le 10^{18}~

Subtask

• Subtask ~1~ ~(50\%)~: ~1 \le n,m \le 5000; 1 \le p_i, t_i \le 10^9~
• Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm

Sample Input 1

5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5

Sample Output 1

2
0
1

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12

Bạn được tham gia trò chơi với dãy gồm ~n~ số nguyên không âm. Trong trò chơi này bạn phải chia dãy đã cho ra thành ~k+1~ đoạn khác rỗng. Để thu được ~k+1~ đoạn bạn cần lặp lại các bước sau đây ~k~ lần:

~1~. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên bạn chỉ có một đoạn - đó chính là dãy ban đầu).

~2~. Chọn một vị trí nào đó giữa hai phần tử của đoạn đã chọn để chia nó ra làm hai đoạn mới khác rỗng.

Mỗi lần thực hiện xong hai bước này bạn nhận được một điểm số bằng tích của hai tổng các số trong hai đoạn mới chia ra.

Yêu cầu: Với cách chơi như trên, bạn hãy tìm cách chơi để đạt được tổng điểm lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(k+1 \le n \le 3000)~

• Dòng thứ hai chứa n số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^4 , 1 \le i \le n)~ là các phần tử của dãy số.

Output

Một số nguyên duy nhất là tổng điểm lớn nhất mà bạn đạt được.

Sample Input

7 3
1 3 4 0 2 3 4

Sample Output

108

Giải thích

Trong ví dụ bạn có thể giành được 108 điểm theo cách sau:

• Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử dụng điểm chia sau phần tử thứ sáu và nhận được: (1 + 3 + 4 + 0 + 2 + 3) × 4 = 52 điểm.

• Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: (1 + 3) × (4 + 0 + 2 + 3) = 36 điểm.

• Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được: (4 + 0) × (2 + 3) = 20 điểm.

Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) và nhận được: 52 + 36 + 20 = 108 điểm.

Subtask

• Có 70% số test tương ứng với 70% số điểm của bài có n ≤ 300;
• Có 30% số test còn lại tương ứng với 30% số điểm của bài có n ≤ 3000.

Cho một cây gồm ~N~ đỉnh. Cạnh thứ ~i~ trên cây có trọng số ~w_i~. Độ dài đường đi giữa hai đỉnh ~u~ và ~v~ được định nghĩa là tổng các cạnh nằm trên đường đi phải qua ít cạnh nhất từ ~u~ tới ~v~. Chọn ~K~ đỉnh lá sao cho tổng độ dài đường đi giữa mọi cặp đỉnh trong ~K~ đỉnh đã chọn là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(1≤K≤N)~.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa thông tin về một cạnh của cây từ nút ~u_i~ đến ~v_i~ với trọng số ~w_i~ ~(1≤w_i≤10^5)~.

Output

• Gồm một số nguyên duy nhất là tổng khoảng cách nhỏ nhất trong cách chọn K nút lá tốt nhất.

Scoring

• Sub1: ~1 ≤ N ≤ 20~;
• Sub2: ~1 ≤ N ≤10^5, K=2~;
• Sub3: ~1 ≤ N ≤2000, K=3~;
• Sub4: ~1 ≤ N ≤10^5, K≤100~.

Example

Input

4 2
1 2 2
1 3 3
1 4 4

Output

5

Input

4 3
1 2 2
1 3 3
1 4 4

Output

18

Chán ngán với các trận chiến cũng như nắm bắt được cơ hội kinh doanh, Satoshi cùng chú pokemon của anh ấy - Pikachu đã lập ra một cửa hàng dịch vụ sạc xe điện.

Một ngày nọ, cửa hàng nhận được ~n~ yêu cầu sạc xe, chiếc xe thứ ~i~ cần ~a_i~ phút để sạc đầy bình. Để công việc diễn ra nhanh chóng, Satoshi sẽ chia ~n~ xe ra thành các nhóm tương ứng với các đoạn con liên tiếp theo số lượng tùy ý. Sau đó, anh ấy sẽ để Pikachu sạc điện cho lần lượt từng nhóm xe. Giả sử nhóm thứ ~i~ gồm các xe có chỉ số trong đoạn ~[l_i,r_i]~, tất cả các xe trong nhóm ~i~ sẽ mất ~charge(i) = max_{j \in [l_i,r_i]}(a_j)~ phút để được sạc.

Gọi ~group(i)~ là nhóm của người thứ ~i~. Thời gian chờ của người thứ ~i~, còn được gọi là ~wait(i)~ được tính bằng tổng thời gian sạc của các nhóm xe trước đó (các nhóm xe có chỉ số bé hơn ~group(i)~) cộng với thời gian sạc của nhóm xe ~group(i)~. Nói cách khác, ~wait(i) = \sum_{j=1}^{group(i)} charge(j)~.

Hãy giúp Satoshi tìm được cách phân chia nhóm tối ưu nhất sao cho tổng thời gian chờ đợi của toàn bộ các khách hàng là nhỏ nhất. Nói cách khác, hãy tối ưu cách chia nhóm sao cho ~\sum_i^n wait(i)~ là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.
  
  

Output

• In ra tổng thời gian chờ đợi nhỏ nhất.
  
  

Constraints

• ~1 \le N \le 10^6~.
• ~1 \le a_i \le 10^9~.
  
  

Subtasks

• Subtask ~1~ ~(20\%)~: ~1 \le n \le 1500~ và ~a_i~ không giảm.
• Subtask ~2~ ~(20\%)~: ~a_i~ không giảm.
• Subtask ~3~ ~(20\%)~: ~a_i~ không tăng.
• Subtask ~4~ ~(20\%)~: ~1 \le n \le 1500~.
• Subtask ~5~ ~(20\%)~: Không có ràng buộc gì thêm.
  
  

Sample Test

Input:

5
1 3 2 6 1

Output:

27

Giải thích: Chia thành hai nhóm ~(1,3,2)~ và ~(6,1)~. Nhóm một mất ~3~ phút để sạc và nhóm ~2~ mất ~6~ phút. Vậy các xe ở nhóm ~1~ phải chờ ~3~ phút và các xe ở nhóm hai phải chờ ~9~ phút.

Đáp án là ~3 + 3 + 3 + 9 + 9 = 27~.