Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LAZYCOWS - Lazy Cows

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274501/problem/D

{assign var="code" value="LAZYCOWS"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

Cho mô hình bãi cỏ có dạng bảng chữ nhật 2xB (1 <= B <= 15,000,000), trong đó một số ô có con bò đang ăn cỏ. Có tất cả N con bò (1 <= N <= 1000) trên bãi cỏ. Ví dụ:

-------------------------------------------------------
|     | cow |     |     |     | cow | cow | cow | cow |
-------------------------------------------------------
|     | cow | cow | cow |     |     |     |     |     |
-------------------------------------------------------

Bác John muốn dùng K (1 <= K <= N) cái chuồng hình chữ nhật để che phủ đàn bò, sao cho tổng diện tích được phủ là nhỏ nhất. Không có hai chuồng nào được nằm đè lên nhau. Hiển nhiên, các chuồng phải che phủ hết các ô có bò.

Ví dụ, trong hình trên nếu K=2, lời giải tối ưu bao gồm một chuồng kích thước 2x3 và một chuồng kích thước 1x4. Tổng diện tích được phủ là 10.

Dữ liệu

Dòng đầu tiên chứa một số nguyên t là số bộ test. Mỗi bộ test có dạng:

  • Dòng 1: N, K, B
  • Dòng 2..N+1: chức tọa độ của các con bò, trong phạm vi (1,1) đến (2,B). Không có ô nào chứa hơn 1 con bò.

Kết quả

Với mỗi test, in ra tổng diện tích nhỏ nhất cần phủ.

Ví dụ

Dữ liệu
1
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

Kết quả
10

{/literal}{elseif ($par=="en" || $par=="")}{literal}

Farmer John regrets having applied high-grade fertilizer to his pastures since the grass now grows so quickly that his cows no longer need to move around when they graze. As a result, the cows have grown quite large and lazy... and winter is approaching.

Farmer John wants to build a set of barns to provide shelter for his immobile cows and believes that he needs to build his barns around the cows based on their current locations since they won't walk to a barn, no matter how close or comfortable.

The cows' grazing pasture is represented by a 2 x B (1 <= B <= 15,000,000) array of cells, some of which contain a cow and some of which are empty. N (1 <= N <= 1000) cows occupy the cells in this pasture:

 

-------------------------------------------------------
|     | cow |     |     |     | cow | cow | cow | cow |
-------------------------------------------------------
|     | cow | cow | cow |     |     |     |     |     |
-------------------------------------------------------

Ever the frugal agrarian, Farmer John would like to build a set of just K (1 <= K <= N) rectangular barns (oriented with walls parallel to the pasture's edges) whose total area covers the minimum possible number of cells. Each barn covers a rectangular group of cells in their entirety, and no two barns may overlap. Of course, the barns must cover all of the cells containing cows.

By way of example, in the picture above if K=2 then the optimal solution contains a 2x3 barn and a 1x4 barn and covers a total of 10 units of area.

Input

The first line of the input contains integer t representing the number of test cases. Then t cases follow. Each case has the following form:

  • Line 1: Three space-separated integers, N, K, and B.
  • Lines 2..N+1: Two space-separated integers in the range (1,1) to (2,B) giving the coordinates of the cell containing each cow. No cell contains more than one cow.

Output

For each test case, output the minimum area required by the K barns in order to cover all of the cows.

Example

Input:
1
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

Output:
10

Input details: As pictured above.

Output details: As discussed above.

{/literal} {/if}


Được gửi lên bởi:Jimmy
Ngày:2005-05-03
Thời gian chạy:9s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:US Open International 2005 Gold Division

hide comments
2018-05-30 16:19:02
chỉ hướng giải với
2017-07-27 09:33:43


Last edit: 2017-07-27 12:42:24
2014-03-25 16:55:51 Anh Duc Le
Bài này cài đặt dễ sai thật. Debug vật vã mới AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.