import java.util.concurrent.CountDownLatch fun main(arr:Array) { val proc = MainProc(readLine()!!.split(" ").map { it.toInt() }) proc.Proc() } class MainProc(inpt:List) { private val pointCount = inpt[0] val maxTotal = inpt[1] private val pointList = (1..pointCount).map { Point(readLine()!!.split(" ").map { it.toLong() }) } private val xDic = getXDic() private val yDic = getYDic() private val xList = xDic.keys.sorted() private val yList = yDic.keys.sorted(); private val area = mutableMapOf>() public fun Proc() { area[xList.first()] = mutableMapOf() if(xDic[xList.first()]!!.containsKey(yList.first())) { val p = xDic[xList.first()]!![yList.first()]!! area[xList.first()]!![yList.first()] = AreaState(1, p.point) } else { area[xList.first()]!![yList.first()] = AreaState(0,0) } for(i in (1 until xList.size)) { val x = xList[i] val y = yList.first() val p = xDic[x]!![y] val prev = area[xList[i-1]]!![y]!! var current = AreaState(prev.pointCount, prev.pointTotal) p?.let { current = AreaState(prev.pointCount + 1, prev.pointTotal + it.point) } area[x] = mutableMapOf() area[x]!![y] = current } for(i in (1 until yList.size)) { val x = xList.first() val y = yList[i] val p = xDic[x]!![y] val prev = area[x]!![yList[i-1]]!! var current = AreaState(prev.pointCount, prev.pointTotal) p?.let { current = AreaState(prev.pointCount + 1, prev.pointTotal + it.point) } area[x]!![y] = current } for(xindex in (1 until xList.size)) { for(yindex in (1 until yList.size)) { val x = xList[xindex] val y = yList[yindex] val p = xDic[x]!![y] val prev1 = area[x]!![yList[yindex-1]]!! val prev2 = area[xList[xindex-1]]!![y]!! val prev3 = area[xList[xindex-1]]!![yList[yindex-1]]!! var current = AreaState(prev1.pointCount + prev2.pointCount - prev3.pointCount, prev1.pointTotal + prev2.pointTotal - prev3.pointTotal) p?.let { current = AreaState(current.pointCount + 1, current.pointTotal + it.point) } area[x]!![y] = current } } var ans = 0 for(xidx in xList.indices) { for(yidx in yList.indices) { for(xidx2 in (xidx..xList.lastIndex)) { for(yidx2 in (yidx..yList.lastIndex)) { val x2 = xList[xidx2] val y2 = yList[yidx2] var point = area[x2]!![y2]!!.pointTotal var count = area[x2] !![y2]!!.pointCount if(xidx > 0) { point -= area[xList[xidx - 1]]!![y2]!!.pointTotal count -= area[xList[xidx - 1]]!![y2]!!.pointCount } if(yidx > 0) { point -= area[x2]!![yList[yidx-1]]!!.pointTotal count -= area[x2]!![yList[yidx-1]]!!.pointCount } if(xidx > 0 && yidx > 0) { point += area[xList[xidx-1]]!![yList[yidx-1]]!!.pointTotal count += area[xList[xidx-1]]!![yList[yidx-1]]!!.pointCount } if(point > this.maxTotal) { continue } ans = Math.max(ans, count) } } } } println(ans) } private fun getXDic():Map> { val ret = mutableMapOf>() for(p in pointList) { if(!ret.containsKey(p.x)) { ret[p.x] = mutableMapOf() } ret[p.x]!![p.y] = p } return ret } private fun getYDic():Map> { val ret = mutableMapOf>() for(p in pointList) { if(!ret.containsKey(p.y)) { ret[p.y] = mutableMapOf() } ret[p.y]!![p.x] = p } return ret } } class Point(inpt:List) { val x = inpt[0] val y = inpt[1] val point = inpt[2].toInt() } class AreaState(val pointCount:Int, val pointTotal:Int)