O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M. Terenul este împărțit în parcele de dimensiune 1x1. Pe unele dintre cele N×M parcele sunt plantați copaci. Firma dorește construirea unui grandios complex comercial și este necesară defrișarea întregului teren. În acest scop sunt utilizați roboți, fiecare robot având baza un pătrat de latură L. Suprafața defrișată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L. Fiecare robot pătrunde prin colțul stânga sus de coordonate (1, 1), se poate deplasa doar în dreapta și în jos și poate părăsi suprafața numai prin colțul dreapta jos, de coordonate (N, M).

Cerinţe

Cunoscând dimensiunile N, M ale terenului și coordonatele parcelelor în care sunt plantați copaci se cere:

1. Numărul minim de roboți necesari defrișării întregului teren.
2. Să se răspundă la Q interogări de forma k, unde k este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrișare cel mult k roboți.

Date de intrare

Fişierul de intrare roboti1.in conţine:

• Pe prima linie un număr natural p reprezentând varianta cerinței de rezolvare. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
• Pe a doua linie se află 3 numere naturale N, M, T separate prin câte un spațiu reprezentând numărul liniilor, numărul coloanelor terenului dreptunghiular, respectiv numărul copacilor plantați.
• Următoarele T linii conțin fiecare câte două numere naturale x y separate prin câte un spațiu, reprezentând linia, respectiv coloana parcelei în care este plantat un copac.
• În cazul cerinței 1, ultima linie conține un singur număr natural L, reprezentând latura unui robot.
• În cazul cerinței 2, penultima linie va conține un număr natural Q, iar ultima linie Q numere naturale k[1], k[2], …, k[Q] separate prin câte un spațiu, reprezentând numărul maxim de roboți ce pot fi utilizați în fiecare dintre cele Q interogări.

Date de ieșire

• Dacă valoarea lui p este 1, se va rezolva numai cerința 1. În acest caz, în fişierul de ieşire roboti1.out se va scrie un singur număr natural n1, reprezentând numărul minim de roboți utilizați.
• Dacă valoarea lui p este 2, se va rezolva numai cerința 2. În acest caz, în fişierul de ieşire roboti1.out se vor scrie Q linii. Fiecare linie i va conţine câte un număr natural ni, reprezentând latura minimă a unui robot astfel încât pentru defrișare să fie utilizați cel mult ki roboți.

Restricții și precizări

• 2 ≤ N, M, L ≤ 150
• 1 ≤ Q ≤ 150
• 1 ≤ k[i] ≤ 150, 1 ≤ i ≤ Q
• 1 ≤ T ≤ 1000
• Latura robotului nu poate fi mai mare decât dimensiunile terenului
• Pe tot parcursul deplasării, fiecare robot se va afla în interiorul suprafeţei terenului.
• În orice moment în interiorul suprafeţei terenului se va afla cel mult un robot.

#include <bits/stdc++.h>
using namespace std;

ifstream in("roboti1.in");
ofstream out("roboti1.out");

int dp[155][155], n, m, t, parc[155][155], x, y, L,  rob, type, answer[155];

int cnt(int ind) {
    int ans = 0;
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= 1; j--) {
            if(parc[i][j]) {
                if(i > ind && j + ind <= m) {
                    dp[i][j] = dp[i - ind][j + ind] + 1;
                } else {
                    dp[i][j] = 1;
                }
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j + 1]);
            }
            ans = max(ans, dp[i][j]);
        }
    }
    return ans;
}

int main()
{
    in >> type;
    in >> n >> m >> t;
    for(int i = 1; i <= t; i++) {
        in >> x >> y;
        parc[x][y] = 1;
    }
    for(int i = 1; i <= 150; i++) {
        answer[i] = cnt(i);
    }
    if(type == 1) {
        in >> L;
        out << answer[L];
    } else {
        int queries;
        in >> queries;
        for(int q = 1; q <= queries; q++) {
            in >> rob;
            int low = 1, high = 150, minLat = -1;
            while(low <= high) {
                int middle = (low + high) / 2;
                if(answer[middle] <= rob) {
                    minLat = middle;
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
            out << minLat << '\n';
        }
    }
    return 0;
}