Условие

Для строительства двумерной пирамиды используются прямоугольные блоки, каждый из которых характеризуется шириной и высотой.

Можно поставить один блок на другой, только если ширина верхнего блока строго меньше ширины нижнего (блоки нельзя поворачивать). Самым нижним в пирамиде может быть блок любой ширины.

По заданному набору блоков определите, пирамиду какой наибольшей высоты можно из них построить.

Примеры

Ввод: 3 3 1 2 2 3 3 Вывод: 5

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

// Функция вычисляет максимальную возможную высоту пирамиды
// Выбирает максимальную высоту блока для каждого уникального основания
private fun pyramid(blocks: List<Pair<Long, Long>>): Long {
    val map = HashMap<Long, Long>() // Словарь для хранения максимальной высоты для каждого основания
    blocks.forEach { block ->
        if ((map[block.first] ?: 0) < block.second) {
            map[block.first] = block.second // Обновляем, если нашли блок большей высоты
        }
    }
    return map.map { it.value }.sum() // Суммируем высоты всех уникальных оснований
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val count = reader.readLine().toInt() // Читаем количество блоков
    val blocks = List(count) {
        val (a, b) = reader.readLine().trim().split(" ").map { it.toLong() }
        a to b // Преобразуем в пары (основание, высота)
    }

    val res = pyramid(blocks) // Вычисляем высоту пирамиды
    writer.write(res.toString())
    writer.newLine()

    reader.close()
    writer.close()
}