소프티어

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/);
const [N, K] = input[0].split(/\s+/).map(Number);
const problems = input.slice(1).map(line => line.trim().split(/\s+/).map(Number));
const colorPositionList = Array.from({length: K + 1}, () => [])




let start
problems.forEach(problem => {
    const [x, y, color] = problem
    colorPositionList[color].push([x, y])
})


let minSize = Number.MAX_SAFE_INTEGER
// 0: 탑, 1: 바텀, 2: 오른, 3: 왼
const top = 0
const bottom = 1
const right = 2
const left = 3
const array = Array.from({length: K + 1},
    () => [Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER])
function dfs(color) {
    colorPositionList[color].forEach(position => {
        // 이전 색상 까지의 위치보다 갱신되어야하면
        if (position[1] > array[color - 1][top]) {
            array[color][top] = position[1]
        }
        else {
            array[color][top] = array[color - 1][top]
        }


        if (position[1] < array[color - 1][bottom]) {
            array[color][bottom] = position[1]
        }
        else {
            array[color][bottom] = array[color - 1][bottom]
        }


        if (position[0] > array[color - 1][right]) {
            array[color][right] = position[0]
        }
        else {
            array[color][right] = array[color - 1][right]
        }


        if (position[0] < array[color - 1][left]) {
            array[color][left] = position[0]
        }
        else {
            array[color][left] = array[color - 1][left]
        }


        // 다음 색이 없으면
        if (color === K) {
            //console.log("현재까지 배열", array)
            minSize = Math.min(minSize, Math.abs((array[color][top] - array[color][bottom]) * (array[color][right] - array[color][left])))
            //console.log("최소 넓이", minSize, Math.abs((array[color][top] - array[color][bottom]) * (array[color][right] - array[color][left])))
        }
        else if (Math.abs((array[color][top] - array[color][bottom]) * (array[color][right] - array[color][left])) < minSize) {
            dfs(color + 1)
        }
    })
}


dfs(1)




console.log(minSize)




/*
입력 크기 작고, 시간 많다 => 모든 경우를 계산해라








 */