LQDOJ CUP 2022 - Round 8

Chắc hẳn ai cũng đã từng có một thời dùng những chiếc điện thoại Nokia, và càng không thể chưa từng chơi tựa game huyền thoại Bounce trên những chiếc "cục gạch" này. Vì muốn sống lại những ký ức tuổi thơ đó, N đã quyết định chọn Bounce làm tựa game cho đồ án cuối kỳ của mình. Với mục tiêu giành được điểm cao, cậu đã làm cho game Bounce của mình phải xịn xò hơn cả bản gốc. Do đó cậu đã tạo ra game Bounce 2D.

Trong tựa game này, quả bóng của chúng ta sẽ di chuyển trong một trục tọa độ Descartes, quả bóng sẽ xuất phát ở tọa độ \((0,0)\) và có kích thước là \(1\). Ban đầu, bạn có thể cho quả bóng xuất phát theo hướng sang phải hoặc lên trên tùy ý. Khi quả bóng đang ở tọa độ \((x,y)\) và kích thước là \(k\) thì quả bóng có thể di chuyển như sau:

• Nếu đang hướng sang phải, quả bóng có thể nhảy tới tọa độ \((x+k,y)\).
• Nếu đang hướng lên trên, quả bóng có thể nhảy tới tọa độ \((x,y+k)\).

Giống như tựa game gốc, Bounce 2D cũng sẽ có những cái bơm và cái đinh. Sẽ có \(n\) tọa độ phân biệt chứa bơm và \(m\) tọa độ phân biệt chứa đinh. Khi quả bóng nhảy vào những tọa độ đặc biệt này thì quả bóng có thể:

• Thay đổi hướng đi của mình từ sang phải thành lên trên và ngược lại hoặc giữ nguyên hướng đi cũ.
• Nếu nhảy vào bơm, quả bóng có thể sử dụng bơm để tăng kích thước của mình lên gấp đôi hoặc giữ nguyên kích thước cũ. Sau khi sử dụng thì cái bơm ở tọa độ đó sẽ không thể sử dụng lại lần nữa.
• Nếu nhảy vào đinh, quả bóng bắt buộc phải giảm kích thước của mình về \(1\).

Bạn sẽ dành chiến thắng nếu đưa quả bóng đi đến chính xác tọa độ \((W,H)\). Hãy cho biết số lần nhảy tối thiểu để có thể dành chiến thắng.

Input

• Dòng đầu tiên chứa bốn số nguyên \(W\), \(H\), \(n\) và \(m\) (\(0 \leq W,H \leq 10^9\), \(0 \leq n,m \leq 5 \cdot 10^4\)) lần lượt là tọa độ của đích, số bơm và số đinh.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) (\(0 \leq x_i \leq W, 0 \leq y_i \leq H\)) là các tọa độ chứa bơm.
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) (\(0 \leq u_i \leq W, 0 \leq v_i \leq H\)) là các tọa độ chứa đinh.
• Dữ liệu đảm bảo không có tọa độ nào có cả bơm và đinh và điểm xuất phát của quả bóng không có bơm hay đinh.

Output

• Một dòng duy nhất chứa một số nguyên duy nhất là số lần nhảy tối thiểu của quả bóng để dành chiến thắng, nếu không tồn tại cách chiến thắng thì in ra \(-1\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(W \leq 10, H = 0\), \(n, m \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(W, H \leq 500\).
• Subtask \(3\) (\(25\%\) số điểm): \(n, m \leq 500\).
• Subtask \(4\) (\(20\%\) số điểm): \(H = 0\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 5 6 6
0 1
0 3
1 1
3 5
3 3
5 2
1 0
2 3
3 1
5 1
5 5
6 1

7

Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử \(0\) hoặc \(1\) và \(1\), các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Những bài toán về dãy Fibonacci đều khá đa dạng về thể loại và chắc hẳn không còn xa lạ gì đối với chúng ta.

Bài toán hôm nay cũng có thể như vậy: Cho hai số nguyên \(n\), \(M\) và dãy số Fibonacci \(F_1, F_2, \ldots, F_n\) thỏa mãn:

Hãy tìm dãy con không giảm dài nhất của dãy \(F_1, F_2,\ldots, F_n\).

Nhắc lại, một dãy con \(F_{i_1}, F_{i_2}, \ldots, F_{i_k}\) mà trong đó \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\) được gọi là không giảm nếu \(F_{i_1} \leq F_{i_2} \leq \ldots \leq F_{i_k}\).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(M\) (\(1 \leq n \leq 10^{18}\), \(1 \leq M \leq 10^3\)).

Output

• Một dòng duy nhất chứa một số nguyên là độ dài của dãy con không giảm dài nhất.

Scoring

• Subtask 1 (\(15\%\) số điểm): \(n \leq 10^3\).
• Subtask 2 (\(15\%\) số điểm): \(n \leq 10^6\).
• Subtask 3 (\(20\%\) số điểm): \(M \leq 3\).
• Subtask 4 (\(25\%\) số điểm): \(M \leq 45\).
• Subtask 5 (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

9 5

7

Liyue là một bến cảng giàu có bậc nhất nằm phía đông đại lục Teyvat. Vùng đất màu mỡ được tạo nên từ những dãy núi cao, rừng đá sừng sững, đồng bằng rộng lớn và những bờ sông nhộn nhịp sức sống, nơi đây rực rỡ sắc màu trong bốn mùa. Là quốc gia được bảo hộ bởi Thần Khế Ước, những hợp đồng và giao kèo luôn được đặt ưu tiên hàng đầu trong các giao dịch giữa các cá nhân hay cơ sở kinh doanh nơi đây.

Ở Liyue có \(n\) cơ sở kinh doanh đánh số từ \(1\) tới \(n\), cơ sở thứ \(i\) có trụ sở tại tọa độ \((x_i,y_i)\) và giữa các cơ sở kinh doanh này có \(n-1\) liên kết trực tiếp giữa các cặp cơ sở kinh doanh nào đó với nhau. Giữa hai cơ sở kinh doanh \(s\) và \(t\) bất kỳ đều tồn tại ít nhất một danh sách các cơ sở \(s = a_1, a_2, \ldots, a_k = t\) sao cho tồn tại liên kết trực tiếp giữa cơ sở \(a_i\) và cơ sở \(a_{i + 1}\) với mọi \(1 \leq i < k\).

Khi cơ sở kinh doanh \(a\) muốn hợp tác kinh doanh với cơ sở \(b\), họ sẽ cần phải hợp tác với \(k\) cơ sở phân biệt \(t_1, t_2,\ldots,t_k\) khác sao cho \(a\) có liên kết trực tiếp với \(t_1\), \(t_1\) có liên kết trực tiếp với \(t_2\), \(\ldots\), \(t_k\) có liên kết trực tiếp với \(b\). Nếu \(a\) và \(b\) có liên kết trực tiếp thì có thể không cần hợp tác thêm với cơ sở nào khác. Để ký kết hợp đồng hợp tác giữa \(k+2\) cơ sở nêu trên, người ta sẽ cần phải tổ chức một cuộc gặp mặt ở một tọa độ \(S(x_s, y_S)\) nào đó làm điểm gặp mặt. Khi đó chi phí di chuyển sẽ là tổng khoảng cách Manhattan giữa \(S\) và trụ sở của \(k+2\) cơ sở nêu trên. Trong tất cả các phương án chọn ra \(k\) cở sở và tọa độ \(S\), hãy cho biết chi phí di chuyển nhỏ nhất là bao nhiêu.

Nhắc lại, khoảng cách Manhattan giữa hai điểm \(A(x_A,y_A)\) và \(B(x_B,y_B)\) là \(|x_A-x_b|+|y_A-y_B|\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(2 \leq n,q \leq 5 \cdot 10^4\)) lần lượt là số cơ sở kinh doanh và số câu hỏi.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\) (\(1 \leq x_i \leq 10^9\)) là tọa độ \(x\) của trụ sở các cơ sở kinh doanh.
• Dòng tiếp theo chứa \(n\) số nguyên \(y_1, y_2, \ldots, y_n\) (\(1 \leq y_i \leq 10^9\)) là tọa độ \(y\) của trụ sở các cơ sở kinh doanh.
• Trong \(n-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i \neq v_i\) (\(1 \leq u_i,v_i \leq n\)) thể hiện rằng giữa \(u_i\) và \(v_i\) có liên kết trực tiếp.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i \neq b_i\) (\(1 \leq a_i,b_i \leq n\)) là câu hỏi thứ \(i\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là chi phí di chuyển nhỏ nhất cho câu hỏi thứ \(i\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n,q \leq 100\).
• Subtask \(2\) (\(15\%\) số điểm): \(x_i, y_i \leq 10\), \(u_i = i, v_i = i + 1\).
• Subtask \(3\) (\(25\%\) số điểm): \(u_i=i, v_i=i+1\).
• Subtask \(4\) (\(20\%\) số điểm): \(x_i, y_i \leq 10\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

4
6
8
5