GCJ2013-Round1A-B.hs

import Data.Function (on)
import Data.List (sortBy)
import Control.Monad (forM_)

solve :: Int -> Int -> [Int] -> Int
solve e r vs = solve' 0 (sortBy (flip compare `on` snd) (zip [0..] vs)) []
  where
    solve' gain [] as = gain
    solve' gain ((i,v):vs) as = solve' (gain + v * a) vs ((i,a,b):as)
      where b = maximum (0:[b' + a - (j-i) * r | (j,a,b') <- as, i < j])
            a = max 0 (minimum (e:[(i-j) * r | (j,_,_) <- as, j < i]) - b)

main :: IO ()
main = do
  t <- readLn
  forM_ ([1..t] :: [Int]) $ \i -> do
    [e,r,_] <- (map read . words) `fmap` getLine
    vs <- (map read . words) `fmap` getLine
    putStrLn $ "Case #" ++ show i ++ ": " ++ show (solve e r vs)