ManageYourEnergy.scala

object ManageYourEnergy{
  def getLocalList(E: Long, R: Long, v: List[Long]): List[Long] = v.take(((E - 1) / R + 1).toInt)
  
  def solve(E: Long,R:Long,v: List[Long]): BigInt = {
    def inner(currE: Long, localList:List[Long], r: BigInt=0): BigInt={
      if(localList.isEmpty) r
      else{
        val spendE = currConsume(currE, E, R, getLocalList(E,R,localList))
        inner(Math.min(currE - spendE + R,E), localList.tail, r + BigInt(spendE) * BigInt(localList.head))
      }
    }
    inner(E,v)
  }

  def currConsume(currE: Long, maxE: Long, R: Long, localList: List[Long]): Long = {
    val max = localList.max
    if (max == localList.head) Math.min(currE, maxE)
    else {
      val idx = localList.find(_ > localList.head) match{
        case Some(n) => localList.indexOf(n)
        case None => 0
      }
      val futureE = currE + (R * idx)
      val futureConsume = Math.min(futureE, maxE)
      Math.max(futureE - futureConsume, 0)
    }
  }
  
  import java.io.{FileInputStream,FileOutputStream}
  
  def main(args: Array[String]) = {
    Console.setIn(new FileInputStream("B-large-practice.in"))
    Console.setOut(new FileOutputStream("B-large-practice.out"))
    val cases = readLine().toInt
    
    (1 to cases).foreach {n =>
      val Array(e , r, _*) = readLine().split(" ").map(_.toLong)
      
      val v = readLine().split(" ").map(_.toLong).toList
      
      println(s"Case #$n: ${solve(e,r,v)}")
    }
  }
}