Maximum Grid

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There is an infinite grid given to you. Some of the cells in this infinite grid have gems in them. Each gem a parameter beauty associated with it which is given by a positive integer.
You will be given an integer L. You have to find maximum sum of beauties inside any square subgrid with its side length being less than or equal to L. Let S be that number, i.e. the maximum sum of beauties for some subgrid with side length no greater than L. You also have to find minimum side length such that there exists some sqaure subgrid with that given side length with sum of beauties of gems inside it being equal to S.
Input
First line of the input contains two space separated N and L, denoting the number of gems and the maximum allowed size of the subgrid, respectively.
Each of the next N lines contains three space separated integers  x_{i}, y_{i} and c_{i} denoting the xcoordinate, ycoordinate and the value of the i^{th} gem respectively.
Output
Output a single line containing two space separated integers: the maximum value of the sum of beauties of gem in some square subgrid of the length not greater than L and the minimum side length of the squaregrid which contains that much sum of beauties of gems inside it, respectively.
Constraints
 1 ≤ L ≤ 10^{5}
 1 ≤ c_{i} ≤ 10^{9}
Subtasks
 Subtask #1 (15 points): 1 ≤ N ≤ 1000, 1 ≤ x_{i}, y_{i} ≤ 2000
 Subtask #2 (25 points): 1 ≤ N ≤ 10^{5}, 1 ≤ x_{i}, y_{i} ≤ 2000
 Subtask #3 (60 points): 1 ≤ N ≤ 10^{5}, 1 ≤ x_{i}, y_{i} ≤ 10^{5}
Example
Input: 3 2 1 1 1 2 1 1 3 1 5 Output: 6 2
Explanation
In the given example, you can create a 2X2 subgrid with topleft corner as (2,1) and bottom right corner as (3,2) with value 6. All other subgrids have value lower than or equal to this subgrid.
Author:  kevind 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/MAXGRID 
Tags  aug16, kevind, medium, segmenttree, sweepline 
Date Added:  28062016 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 