Anh DoMixi là streamer số 1 của MixiLand — thị trấn có ~N~ giao lộ đánh số từ ~1~ đến ~N~ và ~M~ con đường đánh số từ ~1~ đến ~M~ (ban quản lý rất ghiền đánh số).

Mỗi con đường nối hai giao lộ khác nhau theo cả hai chiều (hai chiều vì anh DoMixi không thích đi một chiều). Con đường thứ ~i~ nối giao lộ ~A_i~ và ~B_i~. Không có hai con đường nào cùng nối một cặp giao lộ — MixiLand không lãng phí vật liệu xây dựng như vậy. Mỗi con đường được sơn một màu stream — một số nguyên từ ~1~ đến ~M~. Hiện tại màu của con đường ~i~ là ~C_i~. Nhiều con đường có thể cùng màu vì ban quản lý mua sơn theo lốc giảm giá.

Anh DoMixi vừa cho ra mắt DoBot — một robot giao đồ ăn thần thánh đang đứng ở giao lộ ~1~. Mỗi khi anh hét một màu vào mic, DoBot sẽ ngó xung quanh, tìm đúng con đường mang màu đó đang kết nối với giao lộ hiện tại rồi đi qua. Nghe có vẻ ổn... cho đến khi:

Nếu có nhiều hơn một con đường cùng màu nối với giao lộ hiện tại của DoBot, nó không biết rẽ hướng nào, lag giữa đường rồi đứng hình luôn.

Nhiệm vụ của bạn là điều khiển DoBot từ giao lộ ~1~ đến giao lộ ~N~ — nơi anh DoMixi đang chờ nhận đơn hàng. Để làm được điều này, bạn có thể đổi màu một số con đường trước khi DoBot xuất phát. Chi phí đổi màu con đường ~i~ là ~P_i~ xu (đổi sang bất kỳ màu nào từ ~1~ đến ~M~, tha hồ chọn).

Hãy tính tổng chi phí đổi màu nhỏ nhất để DoBot có thể đến được giao lộ ~N~. Nếu dù sơn phết kiểu gì DoBot vẫn không đến nơi được, hãy in ~-1~ (và gọi ship bằng tay cho anh DoMixi).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~.

~M~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~A_i~, ~B_i~, ~C_i~, ~P_i~.

Kết quả

In ra một số nguyên duy nhất — tổng chi phí đổi màu nhỏ nhất để DoBot đến được giao lộ ~N~. Nếu không thể, in ~-1~.

Ví dụ

Ví dụ 1

Đầu vào:

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

Đầu ra:

3

Ví dụ 2

Đầu vào:

5 2
1 4 1 2
3 5 1 4

Đầu ra:

-1

Ví dụ 3

Đầu vào:

5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1

Đầu ra:

1

Giới hạn

• ~2 \le N \le 100.000~
• ~1 \le M \le 200.000~
• ~1 \le A_i < B_i \le N~
• ~(A_i, B_i) \ne (A_j, B_j)~ với mọi ~1 \le i < j \le M~
• ~1 \le C_i \le M~
• ~1 \le P_i \le 10^9~

Subtask

Năm Ất Tỵ đến, hàng đàn rắn từ khắp nơi đổ về MixiLand ăn mừng — ai bảo đây là năm của chúng cơ chứ? Anh DoMixi, với tinh thần trách nhiệm của một streamer hàng đầu, quyết định ra tay "tiếp đón" lũ rắn theo cách riêng của mình: bắt sạch ~N~ đàn rắn đang xếp hàng dọc theo con đường làng rồi nhốt chúng lại cho gọn.

Anh DoMixi có một cái lưới. Lưới có kích thước ~s~ nghĩa là anh chỉ bắt được đàn rắn có tối đa ~s~ con. Mỗi khi bắt xong một đàn, anh nhốt chúng vào lồng và tiếp tục với đàn tiếp theo bằng lưới trống. Các đàn rắn phải được bắt theo thứ tự từ trái sang phải.

Khi bắt đàn rắn có ~g~ con bằng lưới kích thước ~s~, anh sẽ lãng phí ~s - g~ ô lưới. Anh DoMixi muốn tổng số ô lãng phí càng nhỏ càng tốt — chat toàn nhắc anh phải tiết kiệm mà.

Lưới có thể bắt đầu ở bất kỳ kích thước nào, và anh được phép thay đổi kích thước lưới đúng ~K~ lần trong suốt quá trình bắt rắn (thay đổi có thể tăng hoặc giảm tùy ý).

Hãy giúp anh DoMixi tính tổng số ô lưới lãng phí ít nhất có thể!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~.

Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~, trong đó ~a_i~ là số rắn trong đàn thứ ~i~.

Kết quả

In ra một số nguyên duy nhất — tổng số ô lưới lãng phí nhỏ nhất.

Ví dụ

Đầu vào:

6 2
7 9 8 2 3 2

Đầu ra:

3

Giải thích: Anh DoMixi bắt đầu với lưới kích thước ~7~. Sau đàn 1, anh đổi lên ~9~ và giữ nguyên đến đàn 3. Sau đàn 3, anh đổi xuống ~3~. Tổng lãng phí: ~(7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2) = 3~.

Giới hạn

• ~1 \le N \le 400~
• ~1 \le K < N~
• ~0 \le a_i \le 10^6~

Subtask

Trong một buổi stream đặc biệt, anh DoMixi tìm được một tấm bản đồ kho báu dạng lưới ~n \times n~, mỗi ô chứa một chữ cái in hoa từ A đến Z. Kho báu nằm ở góc dưới bên phải, còn anh đang đứng ở góc trên bên trái — tất nhiên rồi, vì anh DoMixi lúc nào cũng xuất phát từ đầu.

Để đến kho báu, anh chỉ được di chuyển sang phải hoặc đi xuống ở mỗi bước. Dọc đường đi, anh ghi lại các chữ cái trên từng ô anh đi qua (kể cả ô xuất phát và ô đích) tạo thành một xâu độ dài ~2n - 1~.

Chat hỏi: "Anh ơi xâu nào đẹp nhất?" — anh DoMixi, người luôn tối ưu mọi thứ trong cuộc sống, quyết định chọn đường đi sao cho xâu thu được là nhỏ nhất theo thứ tự từ điển.

Hãy tìm xâu đó cho anh!

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~.

~n~ dòng tiếp theo, mỗi dòng chứa ~n~ chữ cái in hoa — mô tả lưới bản đồ.

Kết quả

In ra xâu nhỏ nhất theo thứ tự từ điển có thể thu được.

Ví dụ

Đầu vào:

4
ABCD
BBCA
BBAA
BAAA

Đầu ra:

ABBBAAA

Giải thích: Đường đi tối ưu là ~(0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2) \to (2,3) \to (3,3)~, thu được xâu ~ABBBAAA~. Anh DoMixi đi xuống trước để tránh các chữ C, D ở hàng đầu — chat gật gù hài lòng.

Giới hạn

• ~1 \le n \le 3000~
• Mỗi ô chứa một chữ cái in hoa từ ~\text{A}~ đến ~\text{Z}~

Subtask