Cho số nguyên dương ~x~ ~(1 \le x \le 10^{12})~. Gọi ~S~ là xâu chỉ gồm các kí tự ~0~, ~1~ biểu diễn ~x~ ở hệ nhị phân (không có chữ số ~0~ ở đầu).

Xét mọi xâu con liên tiếp của ~S~. Với mỗi xâu con, coi nó như một số nhị phân (có thể có các chữ số ~0~ ở đầu) và đổi ra giá trị thập phân. Gọi ~T~ là tập các giá trị khác nhau thu được theo cách trên.

Nhiệm vụ của bạn là tính tổng các phần tử trong ~T~.

Yêu cầu

Với số nguyên ~x~, hãy tính ~\sum_{t \in T} t~.

Dữ liệu

Một dòng chứa một số nguyên ~x~.

Kết quả

In ra một số nguyên duy nhất là tổng các số trong tập ~T~ của ~x~.

Ví dụ

Ví dụ 1

Input

5

Output

8

Giải thích

Ví dụ 1

~x=5~ có biểu diễn nhị phân ~S=101~. Các xâu con liên tiếp của ~S~ là: ~1~, ~0~, ~1~, ~10~, ~01~, ~101~. Đổi sang số nhị phân ta được: ~1~, ~0~, ~1~, ~2~, ~1~, ~5~. Lấy các giá trị khác nhau: ~T={0,1,2,5}~, tổng bằng ~0+1+2+5=8~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le x \le 10^{12}~.

Dọc theo một bờ sông (xem như trục số), mỗi sáng có ~n~ người đứng tập thể dục.

Trên bờ sông chỉ có ~m~ đoạn được lát gạch nên có thể đứng tập; các vị trí còn lại không thể đứng. Mỗi đoạn lát gạch được mô tả bởi một đoạn thẳng không giao nhau trên trục số.

Mỗi người sẽ chọn một tọa độ nguyên thuộc một trong các đoạn lát gạch để đứng. Gọi ~d~ là khoảng cách nhỏ nhất giữa hai người đứng gần nhau nhất (tức là ~d = \min_{i \ne j} |p_i - p_j|~). Hãy sắp xếp vị trí đứng để ~d~ lớn nhất.

Yêu cầu

Cho ~n~, ~m~ và ~m~ đoạn ~[a_i, b_i]~ (không giao nhau). Hãy tìm giá trị lớn nhất của ~d~ khi đặt ~n~ người tại các tọa độ nguyên thuộc hợp các đoạn này.

Dữ liệu

• Dòng 1: Hai số nguyên dương ~n~, ~m~ (~2 \le n \le 10^5~, ~1 \le m \le 10^5~).
• Dòng ~i+1~ với ~1 \le i \le m~: Hai số nguyên ~a_i~, ~b_i~ mô tả đoạn lát gạch ~[a_i, b_i]~ (các đoạn không giao nhau, ~|a_i|, |b_i| \le 10^9~, ~a_i \le b_i~).

Kết quả

In ra một số nguyên là giá trị lớn nhất của ~d~. Dữ liệu luôn đảm bảo tồn tại cách sắp xếp để ~d > 0~.

Ví dụ

Ví dụ 1

Input

5 3
0 2
4 7
9 9

Output

2

Giải thích

Ví dụ 1

Có thể đặt ~5~ người tại các vị trí ~0, 2, 4, 6, 9~ (đều thuộc các đoạn đã cho). Khi đó khoảng cách nhỏ nhất giữa hai người gần nhau nhất là ~2~, và không thể đạt giá trị lớn hơn.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 10^5~
• ~1 \le m \le 10^5~
• ~|a_i|, |b_i| \le 10^9~, ~a_i \le b_i~
• Các đoạn ~[a_i, b_i]~ không giao nhau
• Luôn có lời giải với ~d > 0~

Chấm điểm

• ~30%~ số test: ~m \le 10^3~, ~|a_i|, |b_i| \le 10^3~
• ~30%~ số test: ~m \le 10^5~, ~a_i = b_i~
• ~40%~ số test còn lại: không có ràng buộc thêm

Câu lạc bộ Robotics của trường tổ chức một trò chơi trên bàn cờ dạng lưới ~8 \times 8~. Các hàng được đánh số từ ~1~ đến ~8~ (từ trên xuống dưới), các cột được gán nhãn từ ~A~ đến ~H~ (từ trái sang phải). Ban tổ chức đặt vật cản ở một số ô.

Robot của đội bạn bắt đầu tại ô ~A1~ và ban đầu đi theo hướng xuống dưới.

Robot hoạt động theo các quy tắc:

• Robot luôn cố gắng đi thẳng theo hướng hiện tại khi còn có thể.
• Nếu ô ngay phía trước là vật cản hoặc nằm ngoài bàn cờ, robot không thể đi tiếp và sẽ quay sang bên trái hoặc bên phải của hướng hiện tại (bạn được chọn hướng quay ở mỗi lần gặp chướng ngại/biên).
• Robot sẽ dừng lại nếu ô ngay phía trước theo hướng hiện tại là một ô mà robot đã từng đi qua trước đó.

Yêu cầu

Với cấu hình các ô có vật cản đã cho, hãy tìm số ô nhiều nhất mà robot có thể đi qua (tính cả ô xuất phát), nếu bạn được quyền lựa chọn rẽ trái/phải mỗi khi robot bị chặn.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 32~) là số lượng ô có vật cản.

• ~n~ dòng tiếp theo, mỗi dòng là tọa độ một ô có vật cản dưới dạng ~Xk~, trong đó:

  • ~X~ là chữ cái chỉ cột (từ ~A~ đến ~H~),
  • ~k~ là số chỉ hàng (~1 \le k \le 8~).
• Dữ liệu đảm bảo các ô ~A1~ và ~A2~ không có vật cản.

Kết quả

In ra một số nguyên duy nhất là số ô nhiều nhất robot có thể đi qua (kể cả ô xuất phát).

Ví dụ

Ví dụ 1

Input

3
A6
E2
F5

Output

33

Giải thích

Ví dụ 1

Với các vật cản tại ~A6~, ~E2~, ~F5~, nếu lựa chọn rẽ trái/phải hợp lý ở mỗi lần bị chặn, robot có thể đi qua tối đa ~33~ ô trước khi dừng theo quy tắc gặp lại ô đã đi qua.

Ràng buộc và chấm điểm

Ràng buộc

• Bàn cờ kích thước ~8 \times 8~.
• ~1 \le n \le 32~.
• Tọa độ vật cản thuộc các ô hợp lệ, và ~A1~, ~A2~ không có vật cản.

Chấm điểm

• ~40%~ số test có ~n = 1~.
• ~60%~ số test còn lại có ~1 < n \le 32~.

Công ty khai thác khoáng sản có ~n~ mỏ, mỏ thứ ~i~ nằm tại tọa độ ~x_i~ trên một trục số. Mỗi ngày mỏ ~i~ khai thác được ~c_i~ tấn khoáng sản thô. Để giảm chi phí vận chuyển, công ty muốn xây dựng ~k~ nhà máy chế biến.

Cuối mỗi ngày, toàn bộ khoáng sản từ các mỏ sẽ được chở đến nhà máy gần nhất để chế biến. Chi phí vận chuyển ~1~ tấn từ mỏ đến một nhà máy bằng khoảng cách giữa tọa độ mỏ và tọa độ nhà máy đó.

Vị trí xây nhà máy có thể đặt tại bất kỳ điểm nào trên trục số, và cũng có thể trùng với vị trí một mỏ.

Yêu cầu

Hãy chọn ~k~ vị trí đặt nhà máy sao cho tổng chi phí vận chuyển là nhỏ nhất, tức là tối thiểu hóa ~\sum_{i=1}^{n} c_i \cdot \min_{1 \le j \le k} |x_i - p_j|~, trong đó ~p_j~ là tọa độ nhà máy thứ ~j~.

Dữ liệu

• Dòng 1: Hai số nguyên dương ~n~, ~k~ (~1 \le n \le 1000~, ~1 \le k \le 30~, ~k \le n~).
• Dòng 2: ~n~ số nguyên ~x_1, x_2, \dots, x_n~ (~0 \le x_i \le 10^9~).
• Dòng 3: ~n~ số nguyên ~c_1, c_2, \dots, c_n~ (~0 \le c_i \le 10^5~).

Kết quả

In ra một số nguyên duy nhất là tổng chi phí vận chuyển nhỏ nhất.

Ví dụ

Ví dụ 1

Input

4 2
1 2 3 5
1 2 2 3

Output

3

Giải thích

Ví dụ 1

Chọn xây ~2~ nhà máy tại tọa độ ~2~ và ~5~:

• Mỏ ~1~: gần nhất là ~2~, chi phí ~1 \cdot |1-2| = 1~
• Mỏ ~2~: gần nhất là ~2~, chi phí ~2 \cdot 0 = 0~
• Mỏ ~3~: gần nhất là ~2~, chi phí ~2 \cdot 1 = 2~
• Mỏ ~5~: gần nhất là ~5~, chi phí ~3 \cdot 0 = 0~

Tổng chi phí là ~1+0+2+0=3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 1000~
• ~1 \le k \le 30~, ~k \le n~
• ~0 \le x_i \le 10^9~
• ~0 \le c_i \le 10^5~

Chấm điểm

• ~40%~ số test: ~1 \le k \le n \le 20~
• ~20%~ số test: ~1 \le n \le 100~, ~1 \le k \le 30~, ~k \le n~, ~0 \le x_i \le 10^6~, ~1 \le c_i \le 10^3~
• ~40%~ số test còn lại: không có ràng buộc thêm

Alex, một nhà khảo cổ học trẻ, tìm thấy một dãy ~n~ phiến đá được đánh số từ ~1~ đến ~n~, phiến đá thứ ~i~ khắc một số nguyên ~a_i~. Theo cuộn giấy cổ, kho báu sẽ mở nếu tổng giá trị của một dãy phiến đá liên tiếp (một đoạn con) bằng đúng con số bí ẩn ~K~.

Yêu cầu

Cho dãy ~a_1, a_2, \dots, a_n~ và số ~K~, hãy đếm số lượng đoạn con liên tiếp có tổng bằng ~K~.

Dữ liệu

• Dòng 1: Hai số nguyên ~n~, ~K~ (~1 \le n \le 200000~, ~|K| \le 10^9~).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^9~).

Kết quả

In ra một số nguyên duy nhất: số lượng đoạn con liên tiếp có tổng bằng ~K~.

Ví dụ

Ví dụ 1

Input

6 4
-2 3 2 -2 1 5

Output

2

Giải thích

Ví dụ 1

Có đúng ~2~ đoạn con có tổng bằng ~4~:

• Đoạn ~[3, 2, -2, 1]~
• Đoạn ~[-2, 1, 5]~

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 200000~
• ~|K| \le 10^9~
• ~|a_i| \le 10^9~

Chấm điểm

• ~50%~ số test: ~n \le 2000~
• ~50%~ số test: ~n \le 200000~

Trong một dãy vô hạn gồm các số nguyên dương liên tiếp ~1, 2, 3, 4, \dots~, vua Leon đưa ra thử thách như sau:

Với mỗi truy vấn, chọn hai số nguyên dương ~a~ và ~b~, sau đó loại bỏ tất cả các số trong dãy chia hết cho ~a~ hoặc ~b~**. Nhiệm vụ của bạn là xác định số thứ ~K~ trong dãy còn lại (tức là số không bị loại bỏ).

Bạn cần trả lời nhiều truy vấn độc lập.

Yêu cầu

Với mỗi truy vấn gồm ~K, a, b~, hãy tìm số nguyên dương đứng ở vị trí ~K~ trong dãy các số còn lại sau khi loại bỏ mọi số chia hết cho ~a~ hoặc ~b~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 10^5~) là số lượng truy vấn.
• ~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~K, a, b~ (~1 \le K, a, b \le 10^9~).

Các số trên mỗi dòng cách nhau bởi một dấu cách.

Kết quả

Ghi ra ~T~ dòng, mỗi dòng là đáp án của một truy vấn: số thứ ~K~ trong dãy còn lại sau khi loại bỏ.

Ví dụ

Ví dụ 1

Input

2
2 2 4
2 3 4

Output

3
2

Giải thích

Ví dụ 1

• Với ~K=2, a=2, b=4~: loại bỏ các số chia hết cho ~2~ hoặc ~4~ (thực chất là loại bỏ các số chẵn). Dãy còn lại: ~1, 3, 5, 7, 9, \dots~, số thứ ~2~ là ~3~.
• Với ~K=2, a=3, b=4~: loại bỏ các số chia hết cho ~3~ hoặc ~4~. Dãy còn lại bắt đầu: ~1, 2, 5, 7, 10, \dots~, số thứ ~2~ là ~2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le T \le 10^5~
• ~1 \le K, a, b \le 10^9~

Chấm điểm

• ~50%~ số test: ~T, K, a, b \le 100~
• ~50%~ số test còn lại: không có ràng buộc thêm

John nhận được một thử thách Giáng sinh: để mở một hộp quà, cậu phải xử lý một dãy số nguyên không âm ~A~ gồm ~N~ phần tử, được đánh số từ ~1~ đến ~N~, trong đó phần tử thứ ~i~ có giá trị ~A[i]~. John cần thực hiện lần lượt ~M~ thao tác trên dãy, mỗi thao tác thuộc một trong ba loại dưới đây.

Yêu cầu

Thực hiện các thao tác theo thứ tự:

• Loại ~1~: ~1~ ~x~ ~y~ Tính và in ra tổng các phần tử trong đoạn ~[x, y]~, tức ~A[x] + A[x+1] + \dots + A[y]~.
• Loại ~2~: ~2~ ~x~ ~y~ ~w~ Với mọi ~i~ trong ~[x, y]~, cập nhật ~A[i] \leftarrow A[i] \bmod w~.
• Loại ~3~: ~3~ ~x~ ~k~ Gán ~A[x] \leftarrow k~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N~, ~M~ (~1 \le N, M \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A[1], A[2], \dots, A[N]~ (~1 \le A[i] \le 10^9~).

• ~M~ dòng tiếp theo, mỗi dòng mô tả một thao tác:

  • Loại ~1~: ~1~ ~x~ ~y~ (~1 \le x \le y \le N~).
  • Loại ~2~: ~2~ ~x~ ~y~ ~w~ (~1 \le x \le y \le N~, ~1 \le w \le 10^9~).
  • Loại ~3~: ~3~ ~x~ ~k~ (~1 \le x \le N~, ~1 \le k \le 10^9~).

Kết quả

Với mỗi thao tác loại ~1~, in ra một dòng là tổng các phần tử trong đoạn ~[x, y]~ tại thời điểm đó.

Ví dụ

Ví dụ 1

Input

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

Output

14
2

Giải thích

Ví dụ 1

Ban đầu ~A = [1, 5, 3, 2, 4]~.

• Thao tác ~2~: ~2~ ~3~ ~5~ ~3~ ~A[3..5] \leftarrow A[3..5] \bmod 3~ ⟹ ~A = [1, 5, 0, 2, 1]~.
• Thao tác ~3~: ~3~ ~3~ ~6~ ~A[3] \leftarrow 6~ ⟹ ~A = [1, 5, 6, 2, 1]~.
• Thao tác ~1~: ~1~ ~2~ ~5~ In ~A[2] + A[3] + A[4] + A[5] = 5 + 6 + 2 + 1 = 14~.
• Thao tác ~2~: ~2~ ~1~ ~3~ ~2~ ~A[1..3] \leftarrow A[1..3] \bmod 2~ ⟹ ~A = [1, 1, 0, 2, 1]~.
• Thao tác ~1~: ~1~ ~1~ ~3~ In ~A[1] + A[2] + A[3] = 1 + 1 + 0 = 2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, M \le 10^5~
• ~1 \le A[i] \le 10^9~
• Thao tác loại ~1~: ~1 \le x \le y \le N~
• Thao tác loại ~2~: ~1 \le x \le y \le N~, ~1 \le w \le 10^9~
• Thao tác loại ~3~: ~1 \le x \le N~, ~1 \le k \le 10^9~

Chấm điểm

• ~20%~ số test: ~N, M \le 1000~.
• ~20%~ số test: không có thao tác loại ~2~ và ~3~.
• ~20%~ số test: không có thao tác loại ~2~.
• ~20%~ số test: ~w = 2~ trong tất cả các thao tác loại ~2~.
• ~20%~ số test còn lại: không có ràng buộc thêm.

Aran, một nhà thám hiểm, đang tìm đường đi qua một mê cung hình chữ nhật kích thước ~N~ hàng và ~M~ cột để đến góc cuối và lấy viên ngọc vàng. Mỗi ô ~ (i,j) ~ trong mê cung chứa một số nguyên không âm ~a[i,j]~.

Aran bắt đầu tại ô ~ (1,1) ~ (góc trên bên trái) và cần đến ô ~ (N,M) ~ (góc dưới bên phải). Từ ô ~ (i,j) ~, Aran chỉ có thể:

• Đi sang phải: ~ (i,j) \rightarrow (i, j+1) ~
• Đi xuống dưới: ~ (i,j) \rightarrow (i+1, j) ~

Mỗi khi đi qua một ô, Aran thu thập giá trị của ô đó. Một đường đi từ ~ (1,1) ~ đến ~ (N,M) ~ được gọi là hợp lệ nếu tổng các giá trị trên đường đi bằng đúng ~K~.

Yêu cầu

Hãy đếm số lượng đường đi hợp lệ từ ~ (1,1) ~ đến ~ (N,M) ~ sao cho tổng giá trị thu thập được bằng ~K~, và lấy kết quả theo modulo ~10^9 + 7~.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên ~N~, ~M~, ~K~ ( ~1 \le N, M \le 80~, ~0 \le K \le 10^{18}~ ).
• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên không âm ~a[i,j]~ ( ~0 \le a[i,j] \le 10^9~ ) là giá trị các ô trong mê cung.
• Các số trên mỗi dòng cách nhau bởi một dấu cách.

Kết quả

In ra một số nguyên duy nhất: số lượng đường đi hợp lệ từ ~ (1,1) ~ đến ~ (N,M) ~ có tổng bằng ~K~, lấy dư theo ~10^9 + 7~.

Ví dụ

Ví dụ 1

Input

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

Output

2

Giải thích

Ví dụ 1

Có ~2~ đường đi từ ~ (1,1) ~ đến ~ (3,3) ~ có tổng bằng ~6~:

• ~ (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) ~ Tổng: ~1 + 2 + 1 + 1 + 1 = 6~.

• ~ (1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3) ~ Tổng: ~1 + 1 + 1 + 2 + 1 = 6~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, M \le 80~
• ~0 \le K \le 10^{18}~
• ~0 \le a[i,j] \le 10^9~

Chấm điểm

• ~25%~ số test: ~n, m \le 7~.
• ~25%~ số test: ~n, m \le 80~, ~k, a[i,j] \le 1000~.
• ~25%~ số test: ~n \le 14~, ~m \le 20~.
• ~25%~ số test: ~n, m \le 20~, ~0 \le k \le 10^{18}~.

Bạn được cho một dãy số nguyên dương ~A = (a_1, a_2, \dots, a_n)~.

Với hai chỉ số ~i, j~ thỏa ~1 \le i, j \le n~ và ~a_i \ge a_j~, xét giá trị ~a_i \bmod a_j~. Nhiệm vụ là tìm giá trị lớn nhất có thể.

Yêu cầu

Tính ~\max\limits_{1 \le i,j \le n,\ a_i \ge a_j} \left(a_i \bmod a_j\right)~.

Dữ liệu

• Dòng 1: Số nguyên dương ~n~ là độ dài của dãy (~1 \le n \le 2 \cdot 10^5~).
• Dòng 2: ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (mỗi số thỏa ~1 \le a_i \le 10^6~), các số cách nhau bởi dấu cách.

Kết quả

In ra một số nguyên duy nhất là giá trị lớn nhất của ~a_i \bmod a_j~ theo yêu cầu.

Ví dụ

Ví dụ 1

Input

3
2 4 5

Output

1

Giải thích

Ví dụ 1

Các cặp thỏa ~a_i \ge a_j~ cho giá trị lớn nhất là ~5 \bmod 4 = 1~, nên đáp án bằng ~1~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le a_i \le 10^6~

Chấm điểm

• Subtask ~1~ (~50%~): ~n \le 5000~
• Subtask ~2~ (~50%~): ~n \le 2 \cdot 10^5~

Cho dãy số nguyên ~A = (a_1, a_2, \dots, a_n)~ và số nguyên ~m~. Ta gọi một cách chia dãy ~A~ thành ~k~ đoạn con liên tiếp được mô tả bởi dãy chỉ số:

~0 = x_0 < x_1 < x_2 < \dots < x_{k-1} < x_k = n~,

trong đó đoạn thứ ~j~ (với ~1 \le j \le k~) gồm các phần tử: ~a_{x_{j-1}+1}, a_{x_{j-1}+2}, \dots, a_{x_j}~.

Yêu cầu

Hãy chia dãy ~A~ thành ít nhất số đoạn con liên tiếp sao cho tổng các phần tử trong mỗi đoạn không vượt quá ~m~, tức là với mọi ~j~:

~\sum_{i=x_{j-1}+1}^{x_j} a_i \le m~.

Dữ liệu đảm bảo luôn tồn tại ít nhất một cách chia thỏa điều kiện.

Dữ liệu

• Dòng 1: Hai số nguyên dương ~n~, ~m~ (~n \le 10^5~, ~m \le 10^9~).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^9~).

Kết quả

In ra một số nguyên duy nhất ~k~ là số đoạn nhỏ nhất để chia dãy ~A~ thỏa điều kiện.

Ví dụ

Ví dụ 1

Input

11 5
9 -1 2 -6 1 2 3 -4 3 9 -4

Output

3

Giải thích

Ví dụ 1

Một cách chia đạt ~k=3~ là:

• Đoạn ~1~: ~[9, -1, 2, -6, 1]~, tổng ~= 5 \le 5~.
• Đoạn ~2~: ~[2, 3, -4, 3]~, tổng ~= 4 \le 5~.
• Đoạn ~3~: ~[9, -4]~, tổng ~= 5 \le 5~.

Tổng cả dãy là ~14~. Nếu chỉ chia thành ~2~ đoạn thì tổng hai đoạn bằng ~14~, nhưng mỗi đoạn đều phải có tổng ~\le 5~ nên tổng hai đoạn ~\le 10~, mâu thuẫn. Vì vậy cần ít nhất ~3~ đoạn, và đáp án là ~3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~m \le 10^9~
• ~|a_i| \le 10^9~
• Luôn tồn tại cách chia thỏa điều kiện

Chấm điểm

• Subtask ~1~ (~50%~): ~n \le 5000~
• Subtask ~2~ (~50%~): ~n \le 10^5~

Nông dân ~FJ~ mua nhầm 2 máy dẫn đường GPS cho xe của mình. Cả hai máy đều dùng chung một bản đồ gồm ~n~ ngã tư và ~m~ con đường một chiều. Con đường thứ ~i~ đi từ ~A_i~ đến ~B_i~. Có thể có nhiều con đường nối cùng một cặp ngã tư; một con đường hai chiều được hiểu là có đủ hai con đường một chiều ngược hướng.

Nhà của ~FJ~ ở ngã tư ~1~, cánh đồng ở ngã tư ~n~, và luôn tồn tại cách đi từ ~1~ đến ~n~ theo các đường một chiều.

Hai máy GPS khác nhau ở thời gian dự đoán trên từng con đường:

• Máy GPS ~1~ cho rằng đi qua đường ~i~ mất ~P_i~ đơn vị thời gian.
• Máy GPS ~2~ cho rằng đi qua đường ~i~ mất ~Q_i~ đơn vị thời gian.

Khi ~FJ~ đang ở ngã tư ~X~ và đi theo một con đường ~X \rightarrow Y~, mỗi máy GPS sẽ phàn nàn nếu con đường đó không nằm trên bất kỳ đường đi ngắn nhất (theo thời gian của máy đó) từ ~X~ đến ~n~. Nếu cả hai máy cùng phàn nàn ở một bước thì số lượt phàn nàn tăng thêm ~2~.

Yêu cầu

Hãy chọn một đường đi hợp lý từ ~1~ đến ~n~ sao cho tổng số lượt phàn nàn của hai máy GPS là nhỏ nhất.

Dữ liệu

• Dòng 1: Hai số nguyên ~n~, ~m~ (~2 \le n \le 10^4~, ~1 \le m \le 50000~).

• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm bốn số nguyên ~A_i~, ~B_i~, ~P_i~, ~Q_i~:

  • ~1 \le A_i, B_i \le n~
  • ~1 \le P_i, Q_i \le 10^5~
  • biểu diễn một đường một chiều ~A_i \rightarrow B_i~.

Kết quả

In ra một số nguyên duy nhất: số lượt phàn nàn nhỏ nhất mà ~FJ~ phải nghe.

Ví dụ

Ví dụ 1

Input

5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

Output

1

Giải thích

Ví dụ 1

Có thể chọn một đường đi từ ~1~ đến ~5~ sao cho tổng số lần hai máy GPS phàn nàn là nhỏ nhất và bằng ~1~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 10^4~
• ~1 \le m \le 50000~
• ~1 \le P_i, Q_i \le 10^5~
• Luôn tồn tại đường đi từ ~1~ đến ~n~.