-- Main program loop
main = do
    
	-- Hugs might not be able to find the file unless the path is specified
	file <- readFile "input.txt" 
	showLines (lines file) 1

	return ()

-- Do the calculation for each line
showLines :: [String] -> Integer -> IO ()
showLines [] y = return ()
showLines x y = do

	let line = processLine (head x)
	putStr ("Case " ++ show(y) ++ ": " ++ line ++ " units required\n")
		
	showLines (tail x) (y+1)

	return ()

-- Do the calculation for a given line
processLine x = show ( getMinUnits (reverse values) sum 0 )
	where
		tokens = getTokens x
		sum = head (reverse tokens)
		values = init (drop 1 tokens)

-- List of currency units, Remainder, current count, return TotalCount
getMinUnits [] y z = z -- Any empty list returns 0
getMinUnits x y z =	min
	(getMinUnits (tail x) (highAmount y numTimes currentVal) z+numTimes) 
	(getMinUnits (tail x) (lowAmount y numTimes currentVal) z+numTimes+1)
	where
		currentVal = head x
		numTimes = coinsForSum y ( currentVal )

-- Utility functions
coinsForSum x y = abs x `div` y
highAmount x y z = (abs x) - y*z
lowAmount x y z = (abs x) - (y+1)*z

-- Split the string into Integer tokens
getTokens [] = []
getTokens x = (read firstElement::Integer) : getTokens (concatMap (++ " ") tailElements) 
	where
		tokens = words x
		firstElement = head tokens
		tailElements = tail tokens

using System;
using System.IO;

namespace Question5 {

	class Class1 {
	
		static int getMinUnits(int[] types, int offset, int amount, int totalCount) {

			if (offset == -1) return totalCount;

			int thisDenom = types[offset];
			int numTimes = Math.Abs(amount) / thisDenom;

			//Console.WriteLine("Testing amount: " + amount);
			//Console.WriteLine(thisDenom + " numTimes: " + numTimes);

			int newAmount1 = Math.Abs(amount) - numTimes*thisDenom;
			int newAmount2 = Math.Abs(amount) - (numTimes+1)*thisDenom;
			
			//Console.WriteLine(" High: " + newAmount1);
			//Console.WriteLine(" Low: " + newAmount2);

			int high = getMinUnits(types, offset-1, newAmount1, totalCount+numTimes);
			int low = getMinUnits(types, offset-1, newAmount2, totalCount+numTimes+1);

			return Math.Min(high, low);
		}

		static int getInt(string str) {
			return Int32.Parse(str);
		}

		static void Main(string[] args) {
			if (!File.Exists("dataFile5.txt")) {
				Console.WriteLine("Input file not found");
				return;
			}

			StreamReader sr = File.OpenText("dataFile5.txt");

			string input = "";
			
			int index = 0;

			while ((input = sr.ReadLine()) != null) {
				if (input == "") return;

				string[] data = input.Split(' ');

				int numUnits = getInt(data[0]);

				if (data.Length > numUnits + 2 
/* replacing this with: numUnits != data.Length-2 would have won me the contest */ 
					|| numUnits > 10) {
					Console.WriteLine("Case " 
					+ index++ + ": Incorrect number of units: " 
					+ numUnits);
					return;
				}

				int[] unitVals = new int[data.Length-2];
            
				bool foundOne = false;

				for (int i=1; i < data.Length-1; i++) {
					unitVals[i-1] = getInt(data[i]);

					if (unitVals[i-1] > 10000) {
						Console.WriteLine("Case " + index++ 
						+ ": Unit too large");
						continue;
					}

					if (unitVals[i-1] == 1) {
						foundOne = true;
					}
				}

				if (!foundOne) {
					Console.WriteLine("Case " + index++ 
					+ ": Unit of value 1 not found");
					continue;
				}

				int sum = 0;

				try {
					sum = getInt(data[data.Length-1]);
				} catch(FormatException fe) {
					Console.WriteLine("Case " + index++ 
					+ ": Incorrect number of units or missing sum");
				}

				Console.WriteLine("Case " 
				+ index++ + ": " 
				+ getMinUnits(unitVals, unitVals.Length-1, sum, 0) 
				+ " units required");
			}
		}
	}
}