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

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.

Nước HNAMS gồm ~n~ thành phố và đang có kết hoạch liên kết chúng bằng ~m~ con đường cao tốc hai chiều. Các con đường được đánh số từ ~1~ tới ~m~, con đường thứ ~i~ liên kết thành phố ~u_i~ với ~v_i~ và có lợi nhuận là ~w_i~ (các giá trị ~w_i~ phân biệt). Các con đường được thiết kế để tất cả các cặp thành phố đều có thể trực tiếp hoặc gián tiếp đi tới nhau.

Để xây dựng các con đường đó, chính quyền HNAMS quyết định giao việc này cho ~k~ nhà thầu. Sau những vòng bỏ phiếu căng thẳng, các nhà thầu này được xếp ở các vị trí từ ~1~ tới ~k~ thể hiện sự ưu tiên trong việc chọn tuyến đường thi công.

Mỗi nhà thầu sẽ được chọn một tập hợp các con đường trong ~m~ đường cao tốc có sẵn trong kế hoạch, sao cho chúng không tạo ra bất kì chu trình nào và con đường không bị nhà thầu nào trước đó chọn. Giả sử, nếu nhà thầu chọn con đường ~\{1 \rightarrow 2; 2 \rightarrow 3; 3 \rightarrow 1; 4 \rightarrow 5\}~ là không thoả mãn, bởi có chu trình ~1 \rightarrow 2 \rightarrow 3 \rightarrow 1~. Lưu ý rằng ở ví dụ trên mũi tên được đánh hướng cho mục đích biểu diễn, còn trên thực tế thì các con đường là hai chiều.

Đầu tiên, nhà thầu thứ ~1~ sẽ được chọn trước, sau đó tới nhà thầu thứ ~2~, ... rồi tới nhà thầu thứ ~k~. Tất nhiên với cách này, một số con đường sẽ không được xây dựng, nhưng ở giai đoạn đầu của dự án thì đây là chuyện bình thường.

Tất nhiên, mỗi nhà thầu đều muốn tối đa hoá lợi ích của mình, vậy nên khi được chọn các con đường, họ sẽ chọn tập con đường mang tới tổng lợi nhuận lớn nhất có thể.

Nhiệm vụ của bạn là tính toán trước cho chính quyền HNAMS xem mỗi nhà thầu từ ~1~ tới ~k~ sẽ có lợi nhuận là bao nhiêu khi tất cả đều chọn tập con đường một cách tối ưu.

Input

• Dòng đầu tiên gồm ~3~ số nguyên dương ~n, m, k~ miêu tả số thành phố, số con đường cần xây dựng và số nhà thầu.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u_i, v_i, w_i~ miêu tả con đường thứ ~i~ trong kế hoạch, kết nối thành phố ~u_i~ với ~v_i~

Output

• Gồm ~k~ dòng, dòng thứ ~i~ chứa giá trị là tổng lợi nhuận của nhà thầu thứ ~i~ trong cách chia tối ưu.

Subtask

• Trong tất cả các test ~w_i \leq 10^9~

• Có ~20\%~ test tương ứng ~20\%~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k = 1~.

• Có ~25\%~ test tương ứng ~25\%~ số điểm có ~n \le 10^3, m \le 10^4; k \le 1000~.
• Có ~35\%~ test tương ứng ~35\%~ số điểm có ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~.
• ~20\%~ số test còn lại ứng với ~20%~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~.

Sample

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~.