island.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.annotation.tailrec
import scala.collection.parallel.immutable.ParSeq
import scala.io.StdIn


object Main extends App {
      Console.setIn(new FileInputStream("example.in"))

    Console.setIn(new FileInputStream("A-small-practice.in"))
    Console.setOut(new FileOutputStream("A-small-practice.out"))

    Console.setIn(new FileInputStream("A-large-practice.in"))
    Console.setOut(new FileOutputStream("A-large-practice.out"))

    case class Food(p:Int, s:Int)


    def solve(foods:List[Food]): Int = {
        @tailrec
        def step(days:Array[Int], foods:ParSeq[Food]):Int = {
            if (foods.isEmpty) {
                days.max
            } else {
                val food = foods.head
                val nextDays = days ++ days.par.filter(_ <= food.p).map(_ + food.s)
                val maxP = foods.maxBy(_.p).p
                step((nextDays.filter(_ <= maxP) :+ nextDays.max).distinct, foods.tail)
            }
        }

        step(Array(0), foods.sortBy(x => x.p + x.s).par)
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { i => {
        val n = StdIn.readLine().toInt
        val inputs = for (i <- 1 to n) yield {
            val Array(p:Int, s:Int) = StdIn.readLine().split(" ").map(_.toInt)
            Food(p, s)
        }
        println(s"Case #$i: ${solve(inputs.toList)}")
    }}
}