party.hs

module Main where

import           Control.Monad (forM, when)
import           Data.Array.IArray ((!))
import qualified Data.Array.IArray as A

-- input
--   budget
--   parties

-- output
--   cost
--   fun

knapsack :: [(Int, Int)] -> Int -> (Int, Int)
knapsack parties totalBudget = knapsack' 0 totalBudget
  where
    cantParties = length parties
    parties' :: A.Array Int (Int, Int)
    parties' = A.listArray (0, cantParties) parties
    bounds = ((0, 0), (cantParties, totalBudget))
    memo :: A.Array (Int, Int) (Int, Int)
    memo =
      A.listArray bounds
                  [knapsack' i b | (i, b) <- A.range bounds]
    -- knapsack' :: idx -> budgetRest -> (costFin, funFin)
    knapsack' _ 0 = (0, 0)
    knapsack' idx budget
      | idx == cantParties    = (0, 0)
      | budget < partyCost    = nextWithBudget budget
      | otherwise             =
          let (a, b) = nextWithBudget budget
              (c, d) = nextWithBudget (budget - partyCost)
              (c', d') = (c + partyCost, d + partyFun)
          in if b == d' && (a > c' || b > d')
             then (a, b)
             else (c', d')
      where
        (partyCost, partyFun) = parties' ! idx
        nextWithBudget b = memo ! (succ idx, b)

main :: IO ()
main = do
  str <- getLine
  let w1:w2:_ = words str
      totalBudget = read w1 :: Int
      cantParties = read w2 :: Int
  when (totalBudget /= 0 && cantParties /= 0) $ do
    listParties <- forM [1..cantParties] ( \_ -> do
                     str <- getLine
                     let w1:w2:_ = words str
                         partyCost = read w1 :: Int
                         partyFun  = read w2 :: Int
                     return (partyCost, partyFun))
    _ <- getLine -- the blank after parties data
    let (r1, r2) = knapsack listParties totalBudget
    putStrLn (show r1 ++ " " ++ show r2)
    main