"Vệ tinh của chúng ta vừa phát hiện ra một nền văn minh mới ở một hành tinh xa xôi. Chúng ta đã chụp được 1 tấm ảnh low-res có dạng 1 hình vuông $N\times N$ của hành tinh. Bức ảnh cho thấy nhiều dấu hiệu của sự sống văn minh, và các nhà khoa học đã xác định được $m$ điểm đáng quan tâm trên tấm ảnh này. Các điểm trong bức ảnh được đánh số từ $0$ đến $m-1$ ............"

Đấy đã là chuyện của 7 năm trước.

7 năm sau kể từ cái ngày mà bài Aliens đã phổ biến cái thuật toán DP China siêu ảo ma đấy cho các thí sinh trên toàn thế giới, mọi thứ đã thay đổi ít nhiều. Giờ đây, ai cũng biết đến Alien trick. Người người nhà nhà đều biết đến Alien trick. Thằng nhóc lớp 1 mới bập bẹ được 1-2 câu bằng tiếng Anh cũng biết đường nói "Using this formula, all $g_i$ can be computed in $O(n)$ time using Convex Hull Trick optimization, if all $l_i$ and $r_i$ are sorted beforehand. The solution from subtask 5 can also be modified to find the minimum number of photos required to achieve the optimum, call it $p(C)$". Mẹ bạn, bà của bạn và cả cụ của bạn cũng biết đến Alien trick. Mọi bài DP chia đoạn giờ đều trở nên vô nghĩa - cứ ốp Alien trick vào rồi chỉnh công thức truy hồi là AC trong 30s.

Là một coder đã mất hoàn toàn khả năng giao tiếp với gái (human female beings) sau 3 năm ròng chỉ ngồi ru rú trong nhà và 1 đấm AC tất cả các bài trong tất cả các kì thi OI của các nước, khu vực, và quốc tế (và cả liên hành tinh luôn, sau khi nó sẽ được tổ chức lần đầu tiên vào năm sau với sự góp mặt của tầm 1000 thí sinh đến từ sao Hỏa, dự tính là vậy), bạn mong muốn tìm được 1 sinh vật ngoài hành tinh nào đó làm partner để cảm thấy đỡ cô đơn. Tuy nhiên, việc tìm kiếm này xem ra không hề dễ.

Bề mặt của hành tinh được coi là 1 lưới vuông $N\times N$, trong đó các hàng được đánh số từ $1\rightarrow N$, các cột được đánh số từ $1\rightarrow N$. Trên bề mặt hành tinh có $M$ vị trí có thể có bạn đời tương lai của bạn, và bạn muốn khảo sát hết tất cả các điểm này bằng cách chụp các bức ảnh từ 1 vệ tinh mà bạn thuê được. Với mọi $1\le i\le M$, điểm thứ $i$ nằm ở hàng $X[i]$, cột $Y[i]$.

Sau từng ấy năm, ngành công nghệ vũ trụ đã phát triển hơn nhiều. Thay vì chỉ có 1 vệ tinh có quỹ đạo di chuyển trên đường chéo $Y=X$, giờ đã có $P$ vệ tinh, vệ tinh thứ $a$ $(1\le a\le P)$ chỉ có thể di chuyển trên đường chéo có chỉ số là $B[a]$. Đường chéo $b$ gồm tất cả các ô $i$ trên bề mặt hành tinh mà có $X[i]+Y[i]=b$.

Ngành công nghệ chụp ảnh cũng đã tiến bộ hơn rất nhiều: Thay vì mất $1$ đơn vị tiền tệ cho mỗi ô được chụp (không tính lặp), giờ đây, sử dụng kiến thức siêu tà đạo về việc giảm từ 2 chiều xuống còn 1 chiều, các pháp sư Trung Hoa đã khiến cho việc chụp 1 bức ảnh dạng hình vuông $C\times C$ chỉ mất đúng $C$ đơn vị tiền tệ. Tuy nhiên, các vệ tinh vẫn chỉ có thể chụp được các bức ảnh thỏa mãn điều kiện cũ:

• Vùng được chụp bởi mỗi tấm ảnh là 1 hình vuông có 2 góc trái trên và phải dưới thuộc đường chéo là quỹ đạo của vệ tinh đó.
• Tọa độ của cả 4 góc của hình vuông là nguyên. Bức ảnh được phép chụp cả những ô không nằm trong bảng

Dù mọi thứ đã thay đổi nhiều là vậy, vẫn có 1 điều chưa thay đổi: Bạn vẫn nghèo vcl. Vì vậy, bạn cần phải tìm cách chụp tối đa $K$ tấm ảnh sao cho:

• Tất cả các điểm trong số $M$ điểm quan trọng đều được chụp trong ít nhất 1 tấm ảnh
• Tổng chi phí để chụp $K$ tấm ảnh là nhỏ nhất
• Bạn chỉ được phép thuê đúng 1 trong số $P$ vệ tinh để chụp ảnh, vì từ vệ tinh thứ 2 trở đi bạn sẽ phải trả $inf\times (inf^{inf})$ đơn vị tiền tệ (điều này rất tệ cho tình hình kinh tế của bạn và gia đình bạn)

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

6

5 4 2 2
5 7
2 2
2 4
3 3
5 3

4

Giải thích:

• 2 hình vuông màu xanh dương là 1 cách để chụp tất cả các vị trí quan trọng bằng 2 bức ảnh, với chi phí bỏ ra là 8 (không tối ưu)
• Hình vuông màu vàng là 1 cách để chụp tất cả các vị trí quan trọng bằng 1 bức ảnh, với chi phí bỏ ra là 5 (không tối ưu)
• Hình vuông màu đỏ là 1 cách để chụp tất cả các vị trí quan trọng bằng 1 bức ảnh, với chi phí bỏ ra là 4 (tối ưu)