Cho ~n~ đống sỏi được đánh số từ ~1~ đến ~n~. Mỗi đống sỏi thứ ~i~ ban đầu có ~a_i~ viên sỏi.
Hòa đang cầm trong tay ~x~ viên sỏi và muốn phân phối các viên sỏi này vào các đống sao cho sau khi thêm vào, số lượng đống có số viên sỏi là số nguyên tố là nhiều nhất.

Yêu cầu

Hãy tính số lượng đống sỏi có số viên sỏi là số nguyên tố sau khi phân phối tối đa ~x~ viên sỏi.

Dữ liệu nhập vào từ bàn phím

Gồm 2 dòng:

• Dòng 1: Hai số nguyên ~n~ và ~x~ – số lượng đống sỏi và số viên sỏi mà Hòa có
  (~1 \leq n \leq 10^6~, ~0 \leq x \leq 10^6~)
• Dòng 2: ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ – số viên sỏi ban đầu của các đống
  (~1 \leq a_i \leq 10^6~)

Kết quả ghi ra màn hình

Một số nguyên duy nhất là số đống sỏi có số viên là số nguyên tố nhiều nhất có thể đạt được.

Ví dụ

Ràng buộc

• Subtask 1 (30% số điểm): ~n \leq 10^2~
• Subtask 2 (30% số điểm): ~10^2 < n \leq 10^3~
• Subtask 3 (40% số điểm): ~10^3 < n \leq 10^6~

Cho ~n~ đống sỏi được đánh số từ ~1~ đến ~n~. Đống sỏi thứ ~i~ ban đầu có ~a_i~ viên sỏi.
Bình đang cầm trong tay ~x~ viên sỏi và muốn phân phối chúng vào các đống sỏi sao cho:
Tổng số viên sỏi của các đống sỏi có số lượng viên là số nguyên tố là lớn nhất có thể.

Yêu cầu

Tính tổng số viên sỏi lớn nhất của các đống sỏi có số lượng là số nguyên tố sau khi thêm tối đa ~x~ viên.

Dữ liệu nhập vào từ bàn phím

Gồm 2 dòng:

• Dòng 1: Hai số nguyên dương ~n~ và ~x~
  (~1 \leq n \leq 10^4~, ~0 \leq x \leq 10^2~)
• Dòng 2: ~n~ số nguyên dương ~a_1, a_2, ..., a_n~
  (~1 \leq a_i \leq 10^6~)

Kết quả ghi ra màn hình

Một dòng duy nhất ghi số nguyên là tổng số viên sỏi của các đống có số viên là số nguyên tố sau khi thêm tối đa ~x~ viên.

Ví dụ

Ràng buộc

• Subtask 1 (30% số điểm): ~x = 0~
• Subtask 2 (30% số điểm): ~1 \leq x \leq 2~
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm

Cho một đồ thị vô hướng liên thông gồm ~n~ đỉnh đánh số từ ~1~ đến ~n~ và ~m~ cạnh.
Mỗi cạnh nối đỉnh ~u~ và ~v~ có trọng số ban đầu là ~w~.

Với mỗi cạnh, ta có thể tăng trọng số lên một lượng bất kỳ sao cho trọng số mới trở thành số nguyên tố.
Chi phí tăng chính là phần giá trị được cộng thêm (~x~).

Yêu cầu

Tìm đường đi từ đỉnh ~s~ đến đỉnh ~t~, chỉ đi qua các cạnh có trọng số là số nguyên tố,
sao cho tổng chi phí tăng trọng số là nhỏ nhất.

Dữ liệu nhập vào từ bàn phím

• Dòng 1: Bốn số nguyên dương ~n, m, s, t~ (~1 \leq n, m \leq 10^5~, ~1 \leq s, t \leq n~)
• ~m~ dòng tiếp theo: Mỗi dòng chứa ba số nguyên dương ~u, v, w~ (~1 \leq u, v \leq n~, ~1 \leq w \leq 10^6~)

Kết quả ghi ra màn hình

• Một số nguyên là tổng chi phí tối thiểu để đi từ ~s~ đến ~t~ qua các cạnh nguyên tố.
• Nếu không thể đi được, in ra -1.

Ví dụ

Ràng buộc

• Subtask 1 (40% số điểm): ~n, m \leq 2000~
• Subtask 2 (60% số điểm): ~2000 < n, m \leq 10^5~

Cho mảng ~a~ gồm ~n~ phần tử ~a_1, a_2, \ldots, a_n~.
Bạn cần thực hiện thao tác chia mảng sao cho chi phí chia mảng là nhỏ nhất.

Giả sử bạn chia mảng ~a~ thành ~m + 1~ đoạn (với ~m \leq n~) bằng cách chọn ~m~ phần tử tại các vị trí ~b_1, b_2, \ldots, b_m~ (tăng dần) thì chi phí chia mảng của cách chia trên là số lớn nhất trong 2 số sau:

• Tổng của ~m~ số ~a_{b_1}, a_{b_2}, \ldots, a_{b_m}~.
• Tổng lớn nhất trong ~m + 1~ đoạn sau khi chia:
  ~[1, b_1 - 1], [b_1 + 1, b_2 - 1], \ldots, [b_m + 1, n]~
  (tổng đoạn ~[x, y]~ là ~\sum_{i = x}^{y} a_i~, và tổng của đoạn ~[x+1, x]~ được tính là ~0~)

Yêu cầu

Tìm cách chia mảng sao cho chi phí là nhỏ nhất.

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 10^5~) là số phần tử của mảng ~a~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~).

Kết quả ghi ra màn hình

• Một dòng duy nhất là chi phí nhỏ nhất có thể đạt được khi chia mảng.

Ví dụ

Ràng buộc

• Subtask 1 (0.5 điểm): ~1 \leq n \leq 20~
• Subtask 2 (0.5 điểm): ~1 \leq n \leq 100~, ~1 \leq a_i \leq 1000~
• Subtask 3 (1 điểm): Không có ràng buộc gì thêm

Cho ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~.
Hãy tìm số ~X~ nhỏ nhất sao cho ~X~ được tạo thành bằng cách ghép tất cả các chữ số của các số đã cho,
và với mỗi số ~a_i~, ta có thể thu được nó bằng cách xóa một số chữ số (không đổi thứ tự) từ ~X~.

Yêu cầu

Tìm số nguyên dương ~X~ nhỏ nhất thỏa mãn điều kiện:
với mỗi số ~a_i~, có thể tìm được ~a_i~ bằng cách xóa đi một số chữ số (giữ nguyên thứ tự các chữ số còn lại) của ~X~.

Dữ liệu nhập vào từ bàn phím

• Dòng 1: Số nguyên ~N~ (~1 \leq N \leq 10^5~)
• Dòng 2: ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ (~0 < a_i < 10^9~)

Kết quả ghi ra màn hình

• Một dòng duy nhất ghi số nguyên ~X~ nhỏ nhất thỏa mãn yêu cầu.

Ví dụ

Giải thích

• X phải chứa đủ tất cả các chữ số của các số 413, 2007, 29.
• Ví dụ: X = 200241379
  
  • Nếu ta bỏ bớt các chữ số không cần thiết:
  • giữ lại 4 1 3 → được 413
  • giữ lại 2 0 0 7 → được 2007
  • giữ lại 2 9 → được 29
• Đây là số nhỏ nhất thỏa mãn điều kiện đó.

Ràng buộc

• Subtask 1 (25% số điểm): ~N \leq 3~
• Subtask 2 (25% số điểm): ~N \leq 500~
• Subtask 3 (25% số điểm): ~N \leq 10^4~
• Subtask 4 (25% số điểm): Không giới hạn gì thêm (~N \leq 10^5~)

Daisy bắt đầu tại ô ~(0, 0)~ và muốn đến ô ~(w, h)~.
Ban đầu kích thước của cô là ~1~, và mỗi lần cô nhảy theo hướng:

• Sang phải: đến ~(x + k, y)~
• Lên trên: đến ~(x, y + k)~
  (trong đó ~k~ là kích thước hiện tại)

Trên bản đồ có:

• Chai rượu: khi nhảy vào có thể:
  • Không làm gì
  • Uống → kích thước ×2 (chai biến mất)
  • Đổi hướng (hoặc không)
• Yêu quái: khi nhảy vào → kích thước trở về 1 (yêu quái không biến mất)

Yêu cầu

Tìm số bước nhảy ít nhất để Suika đến ~(w, h)~, hoặc in -1 nếu không thể.

Dữ liệu nhập vào từ bàn phím

• Dòng 1: ~w, h, n, m~ — kích thước đích và số chai rượu/yêu quái
  (~0 \leq w, h \leq 10^9~, ~0 \leq n, m \leq 5 \cdot 10^4~)
• ~n~ dòng tiếp: tọa độ chai rượu
• ~m~ dòng tiếp: tọa độ yêu quái

Kết quả ghi ra màn hình

• Một dòng ghi số bước ít nhất hoặc -1.

Ví dụ

Input

3 3 4 4
1 0
3 1
3 3
1 2
3 0
3 2
0 1
0 3

Output

4

Ràng buộc

• Subtask 1 (15%): ~w \leq 10~, ~h = 0~, ~n, m \leq 10~
• Subtask 2 (20%): ~w, h \leq 500~
• Subtask 3 (25%): ~n, m \leq 500~
• Subtask 4 (20%): ~h = 0~
• Subtask 5 (20%): Không ràng buộc thêm