Một nhà máy chế biến hoa quả đang chế biến một sản phẩm từ táo. Nhà máy này đã có một dây chuyền sản xuất gồm nhiều công đoạn. Trong đó công đoạn đầu tiên, có ~N~ quả táo với trọng lượng đã biết được đưa ngẫu nhiên lên băng chuyền thành hàng dọc và được đánh số từ ~1~ đến ~N~. Chúng được ngầm phân thành ~M = [N/K]~ đoạn, mỗi đoạn gồm đúng ~K~ quả (~N~ là bội của ~K~). Các đoạn này cũng được đánh số từ ~1~ đến ~M~, kể từ đầu băng chuyền. Do yêu cầu kỹ thuật, chúng cần được sắp xếp lại sao cho:

• Đoạn ~1~ sẽ gồm ~K~ quả có trọng lượng lớn nhất trong số các quả có mặt trên băng chuyền.

• Nếu ~M > 1~ thì đoạn thứ ~i (i = 2, ..., M)~ sẽ ~K~ quả táo lớn nhất trong số các quả còn lại (không có mặt trong các đoạn từ ~1~ đến ~i-1~).

Một robot sẽ di chuyển dọc theo băng chuyền để thực hiên yêu cầu kỹ thuật nói trên. Mỗi thao tác của robot sẽ gồm việc rút ra khỏi băng chuyền ~1~ quả táo (các quả còn lại được dồn lại) rồi chèn quả táo này vào vị trí thích hợp trên băng chuyền (bao gồm cả vị trí đầu và cuối dãy).

Yêu cầu: Hãy viết chương trình tính xem cần thực hiện ít nhất bao nhiêu thao tác để xếp lại số táo trên băng chuyền theo đúng yêu cầu kỹ thuật.

Input

Vào từ tệp văn bản APROBOT.INP gồm:

• Dòng đầu gồm hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 5000);~

• Dòng thứ hai ghi N số nguyên ~W_i~ ~(1 \le W_i \le 1000, i = 1, 2, ..., N)~ là số đơn vị trọng lượng của quả táo ~i~.

Các số trên cũng mỗi hàng đều được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra tệp văn bản APROBOT.OUT duy nhất một số nguyên, là số thao tác ít nhất robot cần thực hiện.

Scoring

~50\%~ số test ứng với ~50\%~ số điểm của bài có ~(N \le 100)~.

Sample Input 1

6 2
7 3 2 5 9 1

Sample Output 1

2

Sample Input 2

6 2
7 8 9 5 3 5

Sample Output 2

1

Bear là môt nhà du thám (du lịch và thám hiểm) nổi tiếng với khả năng di chuyển và trải nghiệm trong những điều kiện vô cùng khắc nghiệt. Trong chuyến du thám sắp tới, anh sẽ đến với một vùng biển hẻo lánh của biển Nam Thái Bình Dương. Quần đảo này gồm ~N~ đảo (các đảo được đánh số thứ tự từ ~1~ đến ~N~). Việc di chuyển giữa ~N~ đảo này được đáp ứng bởi ~m~ chuyến phà (mỗi chuyến phà đáp ứng nhu cầu di chuyển đi lại giữa hai đảo cố định nào đó), đủ đảm bảo để từ mỗi đảo có thể đến được bất kỳ đảo khác bằng cách trực tiếp hoặc thông qua các tuyến phà trung gian.

Sau khi có được những thông tin cần thiết, Bear đặt ra nhiệm vụ như sau cho chuyến du thám: Chọn ra ~N-1~ trong số ~M~ tuyến phà để thực hiện hành trình đến ~N~ đảo, mỗi đảo ít nhất một lần, sao cho tổng thời gian thực hiện (đơn vị tính là phút) là nhỏ nhất. Bear sẽ đổ bộ xuống đảo ~1~, thực hiện hành trình, quay về đảo ~1~ rồi thoát khỏi máy bay để hoàn thành nhiệm vụ đặt ra. Hành trình có thể phải lặp lại nhiều hơn ~1~ lần đối với một số đảo cũng như tuyến phà.

Các thông tin mà Bear có được bao gồm:

• ~M~ tuyến phà với thời gian di chuyển tương ứng bởi tuyến đó;

• Thời gian mà Bear cần để thoát ra khỏi mỗi đảo kể từ lúc đặt chân đến.

Yêu cầu: Hãy tính xem trong chuyến du thám của mình, Bear có thể hoàn thành nhiệm vụ đặt ra với tổng thời gian nhỏ nhất là bao nhiêu?

Input

Cho trong file văn bản BEAR.INP có cấu trúc như sau:

• Dòng đầu tiên ghi hai số nguyên ~N~ và ~M~ ~(5 \le N \le 10000,\ N < M \le 100000)~;

• Dòng thứ ~2~ ghi ~N~ số nguyên ~S_1,\ S_2,\cdots ,\ S_N~ cho biết: ~S_i~ là số đơn vị thời gian tối thiểu để Bear thoát ra khỏi đảo ~i~ ~(1 \le S_i \le 1000;\ i=1,\ 2,\cdots ,N)~;

• Mỗi dòng trong ~M~ dòng tiếp theo ghi thông tin một tuyến phà bao gồm ~3~ số nguyên ~u,\ v~ và ~T~ ~(1\le u,\ v\le N,\ 1\le T\le 1000)~ với ý nghĩa: ~T~ là số đơn vị thời gian di chuyển theo tuyến phà giữa các đảo ~u~ và ~v~.

Lưu ý: nói riêng tại đảo ~1~, mỗi lần thâm nhập vào đảo này, Bear cũng đều cần thời gian tối thiểu ~S_1~ mới thoát ra khỏi nó.

Output

Ghi ra tệp văn bản BEAR.OUT duy nhất một số nguyên, là tổng thời gian nhỏ nhất mà Bear có thể cần để hoàn thành nhiệm vụ.

Scoring

~50\%~ số Test ứng với ~50\%~ số điểm của bài có ~N \le 1000~

Sample Input 1

6 10
5 2 7 4 5 8
1 3 5
2 3 6
3 1 4
2 4 7
5 6 3
4 5 8
2 6 6
5 3 5
2 5 9
3 4 4

Sample Output 1

105

Một cuộc đua dành cho máy bay không người lái thông minh (UAV cỡ nhỏ) được tổ chức trên một đường băng dài gồm N vạch cách đều nhau, vách cách vạch ~10~ mét. Các vạch được đánh số từ ~1~ đến ~N~. Trên mỗi vạch đều có đặt một bộ cảm biến có nhiệm vụ gửi về trung tâm điều khiển (TTDK) của Ban tổ chức (BTC) cuộc thi số hiệu của vạch khi UAV đứng hay hạ cánh tại vạch này. Cuộc đua cho mỗi UAV được tiến hành như sau: UAV vào đứng tại vạch ~1~, có thời gian ~1~ giây để nạp dữ liệu mà BTC cung cấp, dữ liệu gồm một số nguyên dương ~L~ và ~N~ số nguyên ~X_i~ ~(i=1,\cdots ,n)~ với ý nghĩa ~X_i~ là giá trị của vạch ~i~. Ngay sau đó, UAV phải được thực hiện hành trình bằng cách di chuyển liên tục như sau:

• Trong hành trình lượt đi, UAV (đứng tại vạch ~1~) cần bay đến vạch ~N~ theo quy tắc: Nếu đang đứng ở vạch ~i~ ~(1 \le i \le N)~ thì nó sẽ chỉ được phép hạ cánh tại vạch ~j~ ~(j>i)~ mà ~X_j~ lẻ (ấn định rằng ~X_N=1001~) đồng thời vạch ~j~ cách vạch ~i~ không quá ~L~ vạch (tức là ~1\le j-i \le L)~. Tổng số lần UAV đứng hay hạ cánh trong hành trình lượt đi, bao gồm tại cả vạch ~1~ và vạch ~N~, được ký hiệu bởi ~U~.

• Trong hành trình lượt về, bắt đầu với số điểm được BTC cung cấp bằng ~X_N=1001~, UAV từ vạch ~N~ bay tiếp về vạch ~1~ theo quy tắc: Nếu đang đứng ở vạch ~i~ ~(1<i\le n)~ thì nó sẽ chỉ được phép hạ cánh tại vạch ~k~ ~(k<i)~ mà ~X_K~ chẵn (ấn định rằng ~X_1=1000~). UAV sẽ nhận được thêm ~X_k~ điểm nếu vạch ~k~ cách vạch ~i~ đúng ~L~ vạch (tức ~i-k=L~) và bị trừ ~X_k~ điểm trong trường hợp trái lại. Tổng số điểm mà UAV thu được trong hành trình lượt về, được ký hiệu là ~V~.</p>

Lưu ý:

• Các UAV được lập trình sẵn để tiếp nhận và xử lý dữ liệu của BTC rồi tự động thực hiện toàn bộ hành trình (lượt đi và về).

• Dữ liệu mà BTC đưa ra luôn đảm bảo để các UAV có thể thực hiện được cuộc đua.

Yêu cầu: Hãy lập trình cho UAV để nó đạt được giá trị nhỏ nhất của ~U~ và lớn nhất của ~V~.

Input

Cho trong file văn bản UAV.INP có cấu trúc như sau:

• Dòng đầu ghi số nguyên ~L~ ~(10\le L\le 100)~.

• Dòng thứ ~2~ ghi số nguyên ~N~ ~(L<N\le 500000)~.</p>

• Dòng thứ ~3~ ghi lần lượt các số nguyên ~X_2,\ X_3,\cdots ,\ X_{n-1}~ ~(0\le X_i \le 10^6; i=2,\cdots ,N-1)~.

  Các số trên cùng dòng viết cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra tệp văn bản UAV.OUT ~2~ số nguyên trên ~2~ dòng: Dòng đầu là ~U~ và dòng sau là ~V~.

Scoring

~50\%~ số test ứng với ~50\%~ số điểm của bài có ~N\le 1000~

Sample Input 1

10
19
6 3 15 2 30 7 8 6 10 2 4 9 9 15 0 18 10

Sample Output 1

4
1999