Nhà máy \(V\) đang thử nghiệm \(π-robot\) trên một lưới ô vuông khổng lồ. Một số ô là điểm sạc (chứa ổ cắm điện). Robot lúc đầu đứng ở một ô. Sau khi vận hành, robot sẽ đi qua một số ô, ở mỗi ô một số nguyên dương phút, rồi sau đó sẽ di chuyển sang ô hàng xóm kề cạnh (thời gian di chuyển là không đáng kể). Hãy xác định giá trị lớn nhất có thể của khoảng cách bé nhất từ Robot đến một điểm sạc nào đó sau khi robot vận hành \(N\) phút. Khoảng cách được sử dụng là khoảng cách Manhattan.

Khoảng cách Manhattan giữa hai ô có tọa độ (\(x, y\)) và (\(u, v\)) là \(|x-y| + |u-v|\)

Trong ví dụ trên 4 điểm sạc là các ô màu đen, robot ban đầu ở ô có vòng tròn trắng. Sau 5 phút, robot có thể đến ô (2, -1) và lúc này khoảng cách gần nhất đến một điểm sạc là 7. Và đó là giá trị lớn nhất.

Dữ liệu

• Dòng đầu ghi số điểm sạc \(U\ (1 ≤ U ≤ 10^4)\) và số phút thử nghiệm \(N\ (1 ≤ N ≤ 10^9)\).
• Tiếp theo là \(U\) dòng, mỗi dòng ghi 2 số nguyên là tọa độ một điểm sạc (\(x, y\)).
• Dòng cuối ghi tọa độ lúc ban đầu của robot. Các tọa độ thỏa mãn \(-10^9 ≤ x, y ≤ 10^9\).
• Toàn bộ \(U+1\) điểm đôi một phân biệt.

Kết quả

• In ra giá trị lớn nhất của khoảng cách bé nhất từ robot đến một điểm sạc.

GIỚI HẠN

• 25% số test có \(N ≤ 300\).
• 35% số test có \(N > 300\) và các tọa độ thỏa mãn \(0 ≤ |x|, |y| ≤ 10^3\)
• 40% số test không có giới hạn gì thêm.

Input

4 5 
0 4 
-2 -4 
8 -2 
7 -5 
5 -1

Output

7

Nguồn: Bắc Ninh PREVNOI 2018-2019

Ở cỗ máy bán kem tự động, mỗi que kem được bán với giá 50 cent và máy chỉ chấp nhận các loại đồng xu 50 cent, 1 USD và 2 USD (1 USD = 100 cent). Ban đầu, máy có \(M50\) xu 50 cent, \(M1\) xu 1 USD và \(M2\) xu 2 USD. Tiền thối khi trả 1 USD chỉ được trả nếu máy có đồng 50 cent. Tiền thối khi trả 2 USD chỉ được trả khi máy có \((a)\) một xu 1 USD và một xu 50 cent hoặc \((b)\) ba xu 50 cent. Nếu cả hai trường hợp thỏa mãn, máy luôn chọn phương án \((a)\). Nếu thiếu đồng xu để trả tiền thừa, cỗ máy sẽ không bán kem. Chỗ chứa xu của máy là hữu hạn, nên ở mọi thời điểm, không được có quá \(Mmax\) xu ở mỗi mệnh giá trong máy.

Có \(N\) học sinh đứng trước cỗ máy, và thầy giáo đi kèm cũng có rất nhiều đồng 50 cent, 1 USD, 2 USD. Nhiệm vụ của thầy giáo là phát cho mỗi bạn học sinh một đồng xu để mua đúng một que kem, nếu có dư tiền, học sinh sẽ trả cho thầy giáo, học sinh không trao đổi tiền với nhau.

Hãy đếm xem, thầy giáo có bao nhiêu cách phát xu? Hai cách phát được coi là khác nhau nếu tồn tại một học sinh nhận được đồng xu có mệnh giá khác nhau ở hai cách.

Dữ liệu

• Dòng đầu ghi số \(N\ (1 ≤ N ≤ 300)\) và \(MMAX\ (1 ≤ Mmax ≤ 10000)\).
• Dòng thứ hai ghi ba số nguyên, \(M50, M1, M2\) (\(0 ≤ M50, M1, M2 ≤ Mmax\)) – số lượng các xu mệnh giá 50 cent, 1 USD, 2 USD có trong máy lúc ban đầu.

Kết quả

• In ra số cách phát tiền theo mod (109+9).

GIỚI HẠN

• 30% số test có \(N ≤ 15, MMAX ≤ 10\)
• 35% số test khác có \(16 ≤ N ≤ 50\)
• 35% số test còn lại không có giới hạn gì thêm.

Input

2 2
2 0 0

Output

3

Giải thích: 3 cách trả là:

• 1, 50
• 1, 1
• 1, 20

Input

4 3 
0 0 0

Output

8

Giải thích: 8 cách trả là:

• 50, 50, 50, 1;
• 50, 50, 50, 2;
• 50, 50, 1, 50;
• 50, 50, 1, 1;
• 50, 50, 1, 2;
• 50, 1, 50, 50;
• 50, 1, 50, 1;
• 50, 1, 50, 2;

Nguồn: Bắc Ninh PREVNOI 2018-2019

Cho hai số \(A\) và \(B\) khác nhau (\(1 ≤ A, B < 10, A ≠ B\)), hãy tìm số \(S\) có đúng \(N\) chữ số, mỗi chữ số là \(A\) hoặc \(B\), sao cho phần dư khi chia S cho \(2^N\) là \(K\).

Ví dụ với \(A = 7, B = 2, N = 3\) và \(K = 5\) thì \(S = 277\) là một đáp án.

Dữ liệu

• Dòng đầu ghi 2 chữ số \(A, B\ (1 ≤ A, B < 10, A ≠ B)\).
• Dòng thứ 2 ghi 2 số \(N\ (1 ≤ N ≤ 63)\) và \(K\ (0 ≤ K < 2N)\).

Kết quả

• In ra số \(S\) bất kỳ nếu tồn tại. In ra -1 nếu không tồn tại số \(S\).

GIỚI HẠN

• 20% số test có \(N ≤ 20\)
• 30% số test có \(N ≤ 40\)
• 50% số test còn lại không có giới hạn gì thêm

Input

7 2
3 5

Output

277

Nguồn: Bắc Ninh PREVNOI 2018-2019

Sau khi vô địch AFF Cup 2018, đội tuyển bóng đá Việt Nam được một doanh nghiệp thưởng nóng bằng trò chơi bảng chứa vàng. Trong trò chơi, mỗi cầu thủ phải di chuyển trên một bảng hình chữ nhật \(m×n\), các hàng được đánh số từ 1 đến \(m\) từ trên xuống dưới, các cột được đánh số từ 1 đến \(n\) từ trái qua phải. Ô ở hàng \(i\) cột \(j\) ghi số \(a_{ij}\).

Mỗi cầu thủ được yêu cầu đi từ ô (\(u,v\)) tới ô (\(p,q\)) ($1≤u

Cho hay dãy số nguyên dương \(a_1,a_2,…,a_m\) và \(b_1,b_2,…,b_n\). Các bạn cần xây dựng dãy \(c\) gồm \(k\) phần tử \(c_1,c_2,…,c_k\) thỏa các yêu cầu sau:

• Tồn tại một dãy con của dãy \(c\) là dãy con của dãy \(a\),
• Các phần tử còn lại của dãy \(c\) là một dãy con của \(c\) đồng thời là dãy con của dãy \(b\),
• Dãy \(c\) có thứ tự từ điển nhỏ nhất.

Chú ý: Dãy rỗng được là dãy con của mọi dãy nên nếu dãy \(c\) dãy con của chỉ một trong hai dãy đã cho cũng được coi là thỏa mãn hai điều kiện đầu tiên.

Dữ liệu

• Dòng đầu chứa ba số nguyên \(m,n,k\ (1≤m,n≤3000;k≤m+n)\)
• Dòng thứ hai chứa \(n\) số \(a_1,a_2,…,a_m\).
• Dòng thứ ba chứa \(m\) số \(b_1,b_2,…,n\),

Kết quả

• Ghi ra một dòng duy nhất chứa \(k\) số của dãy \(c\) tìm được.

Input

7 4 9
1 2 1 3 1 2 1
1 2 3 1

Output

1 1 1 1 2 1 2 3 1

Giải thích:

• Dãy con của dãy \(a\) là: 1 1 1 2 1
• Các phần tử còn lại tạo thành dãy con của dãy \(b\) là: 1 2 3 1

Ràng buộc:

• 50% số điểm ứng với các test có \(m,n≤100\)
• 50% số điểm ứng với các test khác không có ràng buộc bổ sung.

Nguồn: Bắc Ninh PREVNOI 2018-2019

Múa Lân là một tiết mục trong lễ hội ăn mừng đội tuyển Việt Nam vô địch AFF Cup 2018. Khi chơi múa lân, hai người trong lốt của một con lân sẽ biểu diễn những tiết mục nhào lộn thăng bằng rất hấp dẫn. Người đứng trước đứng thẳng giữ đầu lân và hai chân có vai trò như hai chân trước của con lân. Người đứng sau cúi xuống lưng người thứ nhất và hai chân có vai trò như hai chân sau của con lân.

Có hai dãy cột, mỗi dãy xếp hàng dọc và đánh số từ 1 tới \(n\), ký hiệu là dãy \(L\) và dãy \(R\). Cột thứ \(i\) của dãy \(L\) và cột thứ \(i\) của dãy \(R\) gọi là ngang hàng nhau. Trong quá trình biểu diễn, chân trái (trước và sau) của con lân chỉ đặt lên cột ở dãy L còn chân phải của nó chỉ đặt lên cột ở dãy R. Mỗi khi đặt chân, hai chân trước luôn đặt ở hai cột ngang hàng và cũng như vậy, hai chân sau cũng luôn phải đặt ở hai cột ngang hàng.

Ban đầu con lân đứng bằng hai chân sau: chân trái ở cột số 1 dãy \(L\) và chân phải ở cột số 1 dãy \(R\) (để thực hiện động tác này người đứng sau phải nâng người đứng trước lên), sau đó con lân đặt hai chân trước lên cột 2 của mỗi dãy. Tiếp theo, con lân sẽ lần lượt nhảy qua dãy cột: mỗi bước nhảy, hai chân trước nhảy sang cặp cột ngang hàng kế tiếp cặp cột đang đứng và hai chân sau nhảy vào vị trí hai chân trước vừa đứng. Để tiết mục biểu diễn được an toàn, dãy các cột phải thỏa mãn hai điều kiện sau:

• Hai cột ở hai vị trí ngang hàng trên hai dãy phải có chiều cao bằng nhau
• Chênh lệnh độ cao giữa hai cột liên tiếp trong dãy \(L\) cũng như chênh lệch độ cao giữa hai cột liên tiếp trong dãy \(R\) không được vượt quá \(Δ\)

Bạn cần kiểm tra nếu dãy cột không tuân thủ quy tắc trên, bạn cần loại bỏ một số ít nhất các cột và dồn các cột còn lại trong mỗi dãy giữ nguyên thứ tự để được hai dãy cột thỏa mãn điều kiện cho buổi diễn. Cho biết độ cao của các cột trong dãy \(L\) sau khi thực hiện công việc (dĩ nhiên đây cũng là độ cao của các cột trong dãy \(R\)). Nếu có nhiều phương án tối ưu, chỉ ra phương án có dãy độ cao của các cột mang thứ tự từ điển lớn nhất.

Dữ liệu:

• Dòng 1 chứa số nguyên dương \(n≤4000\) và số nguyên dương \(Δ≤10^9\)
• Dòng 2 chứa \(n\) số nguyên dương, số thứ \(i\ (i≤10^9)\) là độ cao cột thứ \(i\) của dãy \(L\)
• Dòng 3 chứa \(n\) số nguyên dương, số thứ \(i\ (i≤10^9)\) là độ cao cột thứ \(i\) của dãy \(R\)

Kết quả

• Dòng 1 ghi số lượng cột còn lại trên mỗi dãy (\(m\))
• Dòng 2 ghi \(m\) số nguyên là độ cao của một cột trong dãy \(L\), các số phải được liệt kê theo thứ tự từ chiều cao cột đầu tiên đến chiều cao cột cuối cùng

Các số trên một dòng của input được ghi cách nhau bởi dấu cách

Input

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

Output

4
2 3 4 5

Giải thích:
Trên mỗi dãy có thể giữ lại 4 cột. Có nhiều phương án giữ lại số cột nhiều nhất với chiều cao của các cột là: (2,1,4,5);(2,2,4,5);(2,3,4,5) trong đó phương án (2,3,4,5) có thứ tự từ điển lớn nhất

Ràng buộc:

• 20% số điểm ứng với các test có \(n≤20\)
• 30% số điểm ứng với các test khác có \(n≤100\)
• 50% số điểm ứng với các test khác không có ràng buộc bổ sung

Nguồn: Bắc Ninh PREVNOI 2018-2019