CUBELCM - SUBCUBE EDGE LCM

no tags 

My Friend Deepan Gupta gave me a problem on 3-D and said put it on SPOJ to have some peop fun. You are given a Cube M with size N*N*N, find the subcube S of M, having dimention E*E*E such that E is minimum and sum of all the elements of this subcube is greater than or equal to W. But i found this problem easy and also there are similar problems that already exists on SPOJ. So i made it twist. Now If no such cube exists, print -1. Else if exists with size E, then find the smallest k such that - n divides lcm (m,k) ; m divides lcm (n,k), where n = E^4, m = E^4+1.

Constraints : 0<=M[i][j][k]<=10^9, 1<=i,j,k<=N, 0<=W<=10^15, 1<=N<=100.

Input :
First line contains N,W, size of Cube and Cut-off weight respectively. Next lines contains N matrix. First N lines contains 1st bottom layer of Cube M, next N lines 2nd bottom layer of cube M and so on. Each layer has dimention N*N.

Output :
Print output as stated Above.

Examples :

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

Output :
272

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

Output :
-1


hide comments

Added by:Rishav Goyal
Date:2014-05-10
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own