module Main
where
  
import Text.ParserCombinators.Parsec
import IO hiding (try)
import System.Environment
  
-- PROBLEM-SPECIFIC IMPORTS --  
import Data.List (sort)
import Control.Arrow

------------------------------  
  
-- the input file will be parsed into a list of some type representing  
-- individual cases to be solved by our algorithm:  
type Input = [Case]
  
-- our algorithms will produce a list of some type SolutionCase:  
type Solution = [SolvedCase]

-- we convert each solved case into a String, which is zipped with  
-- the standard "Case #x: " strings for the final output  
type Output = [String]

-- --------------- BEGIN EDITING --------------- --  
  
-- DEFINE A TYPE TO REPRESENT A SINGLE UNSOLVED TEST CASE: --  
type Case =
    -- EXAMPLE: a pair of lists of Ints (our "vectors"):  
    ([Int],[Int])

  
-- DEFINE A TYPE TO REPRESENT A SINGLE SOLVED TEST CASE: --  
type SolvedCase =
    -- EXAMPLE: our Minimum Scalar Product as an Int:  
    Int

  
-- -- -- ALGORITHMS -- -- --  
  
  
-- SOLVE A TEST CASE HERE:  
algorithm :: Case -> SolvedCase
algorithm =
    -- EXAMPLE: simply sort both lists, reverse one, and combine:  
    sum . uncurry (zipWith (*)) . (reverse . sort *** sort)

  
  
-- -- -- PARSING INPUT -- -- --  
  
  
-- DEFINE PARSER FOR A TEST CASE: --  
caseParser :: Parser Case
caseParser = do
    -- EXAMPLE: parses a case consisting of 3 lines: the first describes the   
    -- number n of elements in the following two lines, the next two lines   
    -- have n space-separated elements:  
    w <- word
    let n = read w
    as <- count n word
    bs <- count n word
    return (map read as, map read bs)

  
-- -- -- FORMAT OUTPUT -- -- --  
  
-- DEFINE A FUNCTION FROM AN INDIVIDUAL SolvedCase -> String.   
formatCase :: SolvedCase -> String
formatCase sol =
    -- EXAMPLE: nothing to speak of here:  
    show sol

  
  
-- --------------- STOP EDITING --------------- --  
  
  
--------------------  
-- IO BOILERPLATE --  
--------------------  
  
  
main = do
    -- pass the input file name to our program:  
    (f:_) <- getArgs
    file <- readFile f
      
    -- start parsing, solve problem, and prepare output:   
    let inp = parseWith mainParser file
    solution = map algorithm inp
    solutionStrings = map formatCase solution
    outp = zipWith (++) prefixes solutionStrings
      
    -- write the prepared output to screen:  
    putStr $ unlines outp
  
  
-- dies with error, or returns some datatype with our parsed data:  
parseWith p = either (error . show) id . parse p ""
  
-- to begin parsing, we read in a line containing the number of test cases   
-- to follow. We parse them with caseParser, returning a list:  
mainParser :: Parser Input
mainParser = do
    n <- word
    ms <- count (read n) caseParser
    return ms
   <?> "mainParser"

-- strings to prepend to output:  
prefixes = [ "Case #" ++ show n ++ ": " | n <- [1..]]

  
  
---------------------  
-- VARIOUS PARSERS --  
---------------------  
  
  
-- -- LINE PARSERS -- --  
  
  
-- a single line String, up to the newline:  
wholeLine :: Parser String
wholeLine = manyTill anyChar (try newline) <?> "wholeLine"

-- parse a String with whitespace-separated values into [String]  
whiteSepLine = manyTill spaceSepWord newline <?> "whiteSepLine"

  
-- -- WORD PARSERS -- --   
  
-- a single word followed by whitespace (space, newline, etc.):  
word = do
    w <- many1 nonWhite
    spaces
    return w
   <?> "word"

-- a single word followed by one or more ' ' characters (won't consume '\n')  
spaceSepWord = do
    w <- many1 nonWhite
    many (char ' ')
    return w
   <?> "spaceSepWord"

  
-- e.g. "hello:world" ---> ("hello","world")  
-- won't consume newlines  
    twoWordsSepBy c = do
    x <- manyTill nonWhite (try$ char c)
    y <- many1 nonWhite
    many (char ' ')
    return (x,y)
   <?> "twoWordsSepBy"

  
-- -- CHARACTER PARSERS -- --  
  
-- nonWhitespace character:  
nonWhite = noneOf " \v\f\t\r\n" <?> "nonWhite"