Kadoc là một Producer nổi tiếng trong giới Showbiz. Năm nay, Kadoc muốn tiếng vang sự nghiệp của anh trở nên vang dội hơn. Do đó, anh muốn viết ra một bản nhạc nổi tiếng thế kỉ. Để thực hiện bản nhạc thế kỉ này, Kadoc đã thực hiện thu âm từ ~n~ loại nhạc cụ khác nhau, mỗi bản thu của các loại nhạc cụ có độ lớn âm lượng khác nhau, bản thu của loại nhạc cụ thứ ~i~ có độ lớn âm lượng là ~a_i~. Kadoc cho rằng để một bản nhạc có thể trở thành bản nhạc thế kỉ, âm lượng của các bản thu của các loại nhạc cụ phải thỏa mãn tính chất: $$a_{i+1} = a_i + k$$ Tại một thời điểm, Kadoc có thể chọn ra một bản thu của nhạc cụ bất kì và tăng hoặc giảm một đơn vị độ lớn. Ngoài ra, độ lớn âm lượng sau khi biến đổi cũng phải là số nguyên dương. Kadoc muốn tính toán xem anh sẽ mất ít nhất bao lâu để làm cho bản nhạc của mình trở thành bản nhạc thế kỉ. Hãy giúp Kadoc làm điều đó.

Input

Dòng đầu tiên gồm hai số nguyên ~n, k~ (~1 \le n, k \le 5000~) — lần lượt là số nhạc cụ và giá trị ~k~.

Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~1 \le a_i \le 5000~) — là độ lớn âm lượng của bản thu của loại nhạc cụ thứ ~i~.

Output

Gồm một dòng duy nhất là thời gian ngắn nhất để biến bản nhạc của Kadoc thành bản nhạc thế kỉ.

Scoring

Sample Input 1

5 1
2 1 3 4 5

Sample Output 1

2

Sample Input 2

5 2
2 4 5 4 5

Sample Output 2

9

Notes

Trong test ví dụ thứ nhất, cấu hình của bản nhạc thế kỉ là [~1, 2, 3, 4, 5~].

Trong test ví dụ thứ nhất, cấu hình của bản nhạc thế kỉ là [~1, 3, 5, 7, 9~].

Cho mảng ~a~ có ~n~ phần tử ~a_1, a_2, \cdots, a_n~. Với một dãy con liên tiếp từ ~l~ đến ~r~, bằng cách lấy tổng OR tất cả các số, bạn tìm kiếm thêm được số mới có giá trị là ~a_l~ ~|~ ~a_{l + 1}~ ~|~ ~\cdots~ ~|~ ~a_r~.

Với dãy đã cho và phương pháp tìm kiếm trên, bạn tò mò muốn biết số lượng số phân biệt tối đa có thể tìm kiếm được.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~) — độ dài dãy ~a~.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \cdots, a_n~ (~0 \le a_i \le 10^6~) — giá trị dãy ~a~.

Output

In ra trên một dòng là số lượng số phân biệt tối đa có thể tìm kiếm được từ dãy đã cho.

Scoring

Sample Input 1

3
2 4 0

Sample Output 1

4

Sample Input 2

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

Sample Output 2

11

Notes

Trong ví dụ thứ nhất, gọi ~f(l, r)~ ~=~ ~a_l~ ~|~ ~a_{l + 1}~ ~|~ ~\cdots~ ~|~ ~a_r~. Có thể tìm kiếm các số sau: ~f(1, 1) = 2~, ~f(1, 2) = 6~, ~f(1, 3) = 6~, ~f(2, 2) = 4~, ~f(2, 3) = 4~, ~f(3, 3) = 0~.

Vậy có thể tìm kiếm tối đa ~4~ giá trị phân biệt là ~0, 2, 4, 6~.

Có ~N~ người dân sống ở ~1~ thành phố. Người thứ ~i~ sống ở vị trí ~x_i~ trên trục số và có sức ảnh hưởng là ~e_i~. Chủ tịch của thành phố đang muốn đẩy mạnh phong trào học tin nên họ muốn mọi người trong thành phố đều có sách tin học. Để làm điều này chủ tịch muốn tặng sách cho ~1~ số người trong thành phố và để những người này đi quảng bá sách cho họ. Cụ thể nếu người ~i~ có sách thì người ~j~ cũng sẽ đi mua sách nếu ~|x_i-x_j|\le e_i-e_j~. Hỏi chủ tịch cần phải tặng ít nhất bao nhiêu quyển sách để sau đó mọi người dân đều có sách.

Input

Dòng đầu tiên nhập vào số nguyên dương ~N~ ~(1\le N\le5\cdot10^5)~ chỉ số lượng người dân.

~N~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~x_i~ và ~e_i~ chỉ vị trí và sức ảnh hưởng của người dân thứ ~i~ ~(1\le x_i,e_i \le 10^9)~.

Output

In ra số lượng sách tối thiểu cần phải phát miễn phí cho người dân để sau đó mọi người đều có sách.

Scoring

Sample Input 1

4
4 2
2 3
3 4
6 5

Sample Output 1

2

Sample Input 2

3
7 10
10 10
7 10

Sample Output 2

2

Notes

Giải thích test ví dụ ~1~:

Ví dụ, nếu Chủ tịch quyên tặng sách theo cách sau, tất cả cư dân trong Thành phố sẽ nhận được sách của Chủ tịch.

• Chủ tịch tặng một bản sách cho Cư dân 3.

  • Vì ~|X_3 - X_1| = 1~ và ~E_3 - E_1 = 2~, Cư dân 1 sẽ mua một bản sách của Chủ tịch và nhận được nó.

  • Vì ~|X_3 - X_2| = 1~ và ~E_3 - E_2 = 1~, Cư dân 2 sẽ mua một bản sách của Chủ tịch và nhận được nó.

  • Vì ~|X_3 - X_4| = 3~ và ~E_3 - E_4 = -1~, Cư dân 4 sẽ không mua một bản sách của Chủ tịch.

  Do đó, Cư dân 1, 2, 3 sẽ nhận được sách của Chủ tịch.

• Chủ tịch tặng một bản sách cho Cư dân 4. Vì tất cả cư dân ngoại trừ Cư dân 4 đã nhận được sách của Chủ tịch, cuối cùng tất cả cư dân trong Thành phố đều nhận được sách của Chủ tịch.

Vì không thể quyên tặng sách cho ít hơn hai cư dân mà vẫn đảm bảo tất cả cư dân trong Thành phố nhận được sách của Chủ tịch, nên đầu ra là 2.

Bạn Phương là một hướng dẫn viên du lịch tại đất nước ~X~ có ~N~ thành phố và ~N - 1~ tuyến đường hai chiều, tuyến đường thứ ~i~ có độ dài ~w_i~ nối liền hai thành phố ~u_i~ và ~v_i~. Dữ liệu luôn đảm bảo tồn tại hành trình di chuyển giữa bất kì cặp thành phố nào.

Bạn Phương được chọn một thành phố ~S~ để bắt đầu hành trình, sau đó ghé thăm ~N - 1~ thành phố còn lại, mỗi thành phố đúng một lần, rồi quay trở lại thành phố ~S~ và kết thúc chuyến du lịch. Khi đang ở một thành phố ~u~, bạn Phương có thể thực hiện một trong hai hành động sau:

• Ghé thăm thành phố ~v~ kề với ~u~ thông qua tuyến đường nối hai thành phố đó. Chi phí của hành động này là ~A \cdot w~ với ~w~ là độ dài của tuyến đường.

• Ghé thăm thành phố ~v~ bất kì bằng cách dịch chuyển tức thời đến thành phố đó. Chi phí của hành động này là ~B~.

Yêu cầu: Tính tổng chi phí tối thiểu để thực hiện chuyến du lịch.

Input

Dòng đầu tiên gồm ba số nguyên ~N, A, B~ (~2 \le N \le 200000~; ~1 \le A, B \le 10^9~) – lần lượt là số thành phố và các chi phí để thực hiện hành động.

~N - 1~ dòng tiếp theo gồm các số nguyên ~u_i~, ~v_i~, ~w_i~ (~1 \le u_i, v_i \le N~; ~u_i \neq v_i~; ~1 \le w_i \le 10^9~) – tuyến đường thứ ~i~ nối liền hai thành phố ~u_i~ và ~v_i~, có độ dài là ~w_i~.

Output

Một số nguyên duy nhất là chi phí tối thiểu để thực hiện chuyến du lịch.

Scoring

Sample Input 1

5 9 10
1 4 2
4 5 5
2 5 3
5 3 4

Sample Output 1

50

Sample Input 2

5 2 10
1 4 2
4 5 5
2 5 3
5 3 4

Sample Output 2

38

Cho dãy ~A~ có ~N~ phần tử không âm. Định nghĩa ~f(x, A)~ (với ~x~ là một số nguyên dương ~\leq |A|~) là ~AND~ lớn nhất của mọi dãy con của ~A~ có độ dài ~x~.

Dãy con của A có thể được tạo ra bằng cách xóa đi một vài (có thể là không) phần tử từ dãy ban đầu, các phần tử còn lại phải đảm bảo tính thứ tự ban đầu của nó. Ví dụ, với dãy ~[5, 1, 3, 4]~ thì các dãy con có thể là ~[3], [5, 4], [5, 1, 4]~, nhưng dãy ~[3, 1]~ thì không.

Có ~M~ truy vấn trên dãy ~A~, mỗi truy vấn thuộc 1 trong 3 loại:

• ~1 \space v:~ Chèn giá trị ~v~ vào cuối dãy ~A~.

• ~2 \space v:~ Xóa phần tử mang giá trị ~v~ ra khỏi ~A~, dữ liệu đảm bảo luôn tồn tại ~v~ trong dãy trước khi xóa.

• ~3 \space x~: Tính ~f(x, A)~.

Input

• Dòng đầu gồm 3 số nguyên ~N, M, k~ ~(1 \leq N, M \leq 75000, 1 \leq k \leq 18)~.

• Dòng tiếp theo gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(0 \leq a_i < 2^k \space)~ là các phần tử ban đầu của dãy ~A~.

• Mỗi dòng trong ~M~ dòng tiếp theo chứa 1 trong 3 truy vấn ~1 \space v~, ~2 \space v~, hoặc ~3 \space x~ ~(0 \leq v < 2 ^ k, 1 \leq x \leq |A|~).

Output

• Với mỗi truy vấn loại ~3~, in ra một số nguyên duy nhất là kết quả của ~f(x, A)~ trên một dòng.

Scoring

Sample Input 1

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

Sample Output 1

6
4
6
5

Notes

Những dãy con mang lại kết quả tối ưu là ~(6, 7); (6, 7, 5); (6, 7, 7); (7, 5)~