ზარმაცი ძროხები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2004/05, OPEN


ფერმერი ჯონის ახალი სასუქი საძოვარზე ისე სწრაფად ზრდის ბალახს, რომ ძროხებს
გადაადგილება აღარ სჭირდებათ. შედეგად ძროხები გასუქდნენ და გაზარმაცდნენ...
ზამთარი კი კარზე აკაკუნებს. 
     ფჯ-ს სურს ააგოს ბოსლები თავისი ზანტი ძროხებისათვის და ფიქრობს, რომ
საკმარისი იქნება ბოსლების აგება ძროხების ამჟამინდელი ადგილსამყოფლების გარშემო,
რადგან ზარმაც ძროხებს არ სურთ თუნდაც 1 სანტიმეტრზე გადაადგილებაც. 
     საძოვარი წარმოდგენილია  2 x B (1 <= B <= 15,000,000) უჯრედთა მასივის
სახით. ზოგ უჯრედში იმყოფება ძროხა, ხოლო ზოგი - ცარიელია. სულ საძოვარზე
იმყოფება N (1 <= N <= 1000) ძროხა.

-------------------------------------------------------
|     | cow |     |     |     | cow | cow | cow | cow |   cow-ძროხა 
-------------------------------------------------------
|     | cow | cow | cow |     |     |     |     |     |
-------------------------------------------------------

     ფჯ-ს სურს ააგოს მხოლოდ K (1 <= K <= 1000) მართკუთხა ფორმის ბოსელი 
(ბოსელთა კედლები საძოვრის გვერდთა პარალელური უნდა იყოს), რომელთა საერთო 
ფართობი უჯრედების მინიმალურ რაოდენობას დაფარავს. ყოველი ბოსელი მთლიანად 
ფარავს უჯრედების მართკუთხა ჯგუფს და ბოსლების არცერთი წყვილი არ თანაიკვეთება.
ცხადია, რომ ბოსლებმა უნდა გადაფარონ ყველა ის უჯრედი, რომლებიც ძროხას 
შეიცავენ.
     მაგალითად თუ მოცემული ნახაზისთვის K=2, მაშინ ოპტიმალური ამოხსნა 
შეიცავს 2x3 და 1x4 ზომის ბოსლებს და მათ მიერ დაფარული საერთო ფართობია 10. 

შეტანის ფორმატი:
* სტრიქონი 1: ჰარით გაყოფილი სამი მთელი რიცხვი: N, K, B.
* სტრიქონები 2..N+1: ჰარით გაყოფილი ორი მთელი რიცხვი დიაპაზონში (1 1)-დან
                               (2 B)-მდე, რომლებიც განსაზღვრავენ ძროხის შემცველი ერთი  
                              უჯრედის კოორდინატებს. არცერთი უჯრედი არ შეიცავს ერთზე მეტ ძროხას.

შეტანის განმარტება:
მაგალითი შეესაბამება ზემოთ მოყვანილ ნახაზს.

გამოტანის ფორმატი:
* სტრიქონი 1: მინიმალური ფართობი, რომელიც საჭიროა К ბოსლით ყველა ძროხის დასაფარავად.




მაგალითები

შესატანი მონაცემები
8 2 9 1 2 1 6 1 7 1 8 1 9 2 2 2 3 2 4 დაკოპირება
გამოსატანი მონაცემები
10 დაკოპირება