PreVOI 2018-2019 - Ngày 1

Nhà máy \(V\) đang thử nghiệm \(\pi\text{-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-u| + |y-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.

Input

• Dòng đầu ghi số điểm sạc \(U\ (1 \le U \le 10^4)\) và số phút thử nghiệm \(N\ (1 \le N \le 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 \le x, y \le 10^9\).
• Toàn bộ \(U+1\) điểm đôi một phân biệt.

Output

• 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.

Example

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

7

Scoring

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

Ở 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\text{ USD} = 100\text{ 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.

Input

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

Output

• In ra số cách phát tiền theo \(\text{modulo } 10^9+9\).

Example

2 2
2 0 0

3

4 3 
0 0 0

8

Scoring

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

Cho hai số \(A\) và \(B\) khác nhau (\(1 \le A, B < 10, A \neq 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.

Input

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

Output

• 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\).

Example

7 2
3 5

277

Scoring

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

Notes

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