//luam fiecare diagonala
//cautam subsecvente de numere care insumate dau mai putin de W
//verificam daca si cealalta diagonala a matricei pe care o formeaza da mai putin de W
//verificam daca suma celor 2 diagonale da mai putin de W

#include<fstream>
#include<stdio.h>
using namespace std;

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

int x[1000][1000];

int gaseste_matricea_speciala( int n, int w){

    int latura = 0;
    //array in care vom pune diagonalele si un counter
    int counter = 0;
    for (int slice = 1; slice < 2 * n - 2; ++slice) {
    	printf("Slice %d: ", slice);
    	int z = slice < n ? 0 : slice - n + 1;
        //lungimea sliceului
        int slice_size = slice - 2*z + 1;
        printf("\n");
    	for (int j = z; j <= slice - z; ++j) {
            int sum = 0;
            int counter = 0;
            for(int it = j; it <= slice - z; it++){
                counter++;
                //printf("Counter = %d \n", counter);
                sum += x[it][slice - it];
                printf("Number of items = %d and item = %d on position %d , %d\n", slice-z, x[it][slice - it], it, slice-it);
                //punem diagonala in arrayul nostru ca sa verifica daca are subsequence cu suma < W
                //printf("Bagam %d la pozitia %d \n", x[j][slice - j], counter);
                //printf("it = %d j = %d \n", it, j);
                if(sum <= w && it > j){
                    int second_sum = 0;
                    if(it - j > latura){
                        //avem coordonatele in matrice: x[it][slice - it]. aflam corespondentul in cealalta diagonala
                        printf("Opusul este numarul: %d \n", x[it][slice-it+counter-1]);
                        printf("Urmatorul numar pe diagonala secundara: %d \n", x[it-1][slice-it+counter-1-1]);
                        for(int secundara = 0; secundara < counter; secundara++)
                            second_sum += x[it-secundara][slice-it+counter-1-secundara];
                            if (second_sum + sum > w)
                                break;
                    }
                    if (second_sum + sum <= w){
                        latura = counter;
                        printf("S-a gasit submatricea speciala");
                    }

                }


            }
    return latura;
}
    }
}

int main(){
    printf("Test1");
    int t = 0, n = 0, w = 0;
    in>>t;

    for(int numar = 0; numar < t; numar++){
        in>>n;
        in>>w;
        //citim matricea
        for(int a = 0; a < n; a++)
            for(int b = 0; b < n; b++)
                in>>x[a][b];
       out<<gaseste_matricea_speciala(n,w)<<"\n";
    }


    //tinem rezultatul partial

            ///////////////////////////////////////old approach//////////////////////////////////////////
            /*
            if(j == slice - z && 1 == 0)
                //verificam in n^2
                for (int x = z; x <= slice - z; ++x) {
                    //suma temporara a elementelor din subsequence de pe diagonala

                    for(int y = x; y < counter; y++){
                        //printf("Iterare: y = %d ; x = %d ; counter = %d \n", y, x, counter);
                        //sum = sum + x[j][slice - j];
                        //printf("\nIteram elementul %d %\n", x[j][slice - j]);
                        //daca suma e mai mica ca 5 si nu suntem la primul element din subsequence retinem subsequencul
                        if(sum < 5 && y > x){
                            //daca suma pe care am descoperit-o este formata din mai multe elemente ca L, mergem mai departe
                            if(y - x > latura)
                                //va trebui sa aflam diagonala aferenta matricei formate din sirul de elemente pe care l-am gasit
                                //daca suma de pe cealalta diagonala plus suma de pe diagonala noastra e mai mica decat W, updatam latura in global
                                //for(int index = j )
                                printf("Coloana = %d Linia= %d \n", slice-j, j);

                        }
                        //bugfix?
                        if(y == counter - 1)
                            break;
                    }
                        printf("\nGATA UN SUBSEQUENCE\n");
                }
            */


    	//printf("\n");
        //resetam counterul arraylui temporar de diagonale
        //counter = 0;
        return 0;
}