Largest Cube Stack Height Algorithm

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace CubeAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var pairs = ParseInputFile();
            if (pairs.Count == 0)
            {
                Console.WriteLine("There are no input pairs.");
                Console.ReadKey();
                return;
            }

            //they need to be ordered
            pairs = pairs.OrderByDescending(c => c.Item1).ThenByDescending(c => c.Item2).ToList();

            List<List<Tuple<int, int>>> lists = new List<List<Tuple<int, int>>>();

            //each pair needs to be touched only once
            foreach (var pair in pairs)
            {
                //find the list with highest segment
                int maxLength = 0;
                int maxHeight = 0;
                int listIndex = -1;
                for (int j = 0; j < lists.Count; j++)
                {
                    var heightLength = Find(lists[j], pair);

                    if (heightLength.Item1 > maxHeight)
                    {
                        maxHeight = heightLength.Item1;
                        maxLength = heightLength.Item2;
                        listIndex = j;
                    }
                }

                if (listIndex == -1)
                {
                    //this pair can't fit anywhere, new list is made
                    List<Tuple<int, int>> list = new List<Tuple<int, int>>();
                    list.Add(pair);
                    lists.Add(list);
                }
                else if (maxLength < lists[listIndex].Count)
                {
                    //this item fits somewhere in the middle of an existing list
                    //a new list is made as a copy of the current up to the point where it can't fit
                    List<Tuple<int, int>> list = new List<Tuple<int, int>>();
                    for (int i = 0; i < maxLength; i++)
                    {
                        list.Add(lists[listIndex][i]);
                    }
                    list.Add(pair);
                    lists.Add(list);
                }
                else
                {
                    //this item fits at the end (maxlength is the size of the current list)
                    lists[listIndex].Add(pair);
                }
            }

            //writing all lists and finding the first highest one in the same loop (to save precious nanoseconds)
            Console.WriteLine("Lists:");
            int max = 0;
            int maxIndex = -1;
            for (int j = 0; j < lists.Count; j++)
            {
                int height = 0;
                for (int i = 0; i < lists[j].Count; i++)
                {
                    height += lists[j][i].Item1;
                }

                if (height > max)
                {
                    max = height;
                    maxIndex = j;
                }

                Display(lists[j]);
                Console.WriteLine();
            }

            Console.WriteLine();
            Console.WriteLine("Maximum height list, with a height of {0}:", max);
            if (maxIndex != -1)
                Display(lists[maxIndex]); //the list with maximum height
            Console.ReadKey();
        }

        //finds the maximum height and the position for the item to stack on the list
        static Tuple<int, int> Find(List<Tuple<int, int>> list, Tuple<int, int> item)
        {
            //Could be transformed into a binary search for larger problems,
            //the it would be O(N log N) on the worst case i guess, but with n <= 100 it doesn't really matter
            //I estimate normal search worst case to be O(N^2)
            int currentHeight = 0;
            int currentLength = 0;
            for (int i = 0; i < list.Count; i++)
            {
                if (!CanStack(list[i], item))
                    break;

                currentHeight += list[i].Item1;
                currentLength = i + 1;
            }
            return new Tuple<int,int>(currentHeight, currentLength);
        }

        static bool CanStack(Tuple<int, int> below, Tuple<int, int> above)
        {
            return below.Item1 >= above.Item1 && below.Item2 >= above.Item2;
        }

        static void Display(List<Tuple<int, int>> results)
        {
            foreach (var item in results)
                Console.Write(item + " ");
        }

        static List<Tuple<int, int>> ParseInputFile()
        {
            List<Tuple<int, int>> cubes = new List<Tuple<int, int>>();

            FileInfo file = new FileInfo("Input.txt");
            using (StreamReader sr = new StreamReader(file.OpenRead()))
            {
                if (!sr.EndOfStream)
                    sr.ReadLine(); //the first, unnecessary line: number of pairs...
                while (!sr.EndOfStream)
                {
                    string line = sr.ReadLine().TrimEnd(' ');
                    if (string.IsNullOrWhiteSpace(line))
                        continue;

                    string[] parts = line.Split(' ');
                    if (parts.Length != 2)
                        throw new Exception(String.Format("Parse error at line '{0}'", line));

                    int first = 0;
                    int second = 0;
                    if (!int.TryParse(parts[0], out first))
                        throw new Exception(String.Format("Parse error at line '{0}'", line));

                    if (!int.TryParse(parts[1], out second))
                        throw new Exception(String.Format("Parse error at line '{0}'", line));

                    cubes.Add(new Tuple<int, int>(first, second));
                }
            }

            return cubes;
        }
    }
}