Solving the Mining algorithm from HackerRank

Question

I was working on this problem for a few hours last night and finally came up with a brute-force solution. The task is to report the minimum work necessary (sum of weight × distance) to relocate gold produced at n mines to k of those mines. The first line of input contains n and k; subsequent lines give the location and amount of gold of each mine.

My solution is passing all the unit tests that don't time out, so I'm fairly confident that is correct except that it needs to use fewer operations in order to be a successful submission.

Any ideas on how I can make this not timeout?

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

static class Extensions 
{
     // ripped from http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n   
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
    {
      return k == 0 ? new[] { new T[0] } :
        elements.SelectMany((e, i) =>
          elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
    }
}

class Mine
{
    public int Distance { get; set; } // from river
    public int Gold { get; set; } // in tons
}

class Solution 
{
    static void Main(String[] args) 
    {
        // helper function for reading lines
        Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

        int[] line1 = LineToIntArray(Console.ReadLine());
        int N = line1[0], // # of mines
            K = line1[1]; // # of pickup locations

        // Populate mine info
        List<Mine> mines = new List<Mine>();
        for(int i = 0; i < N; ++i)
        {
            int[] line = LineToIntArray(Console.ReadLine());
            mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
        }

        // helper function for checking whether a move combination ends up 
        // forming K groups
        Func<IEnumerable<Tuple<Mine,Mine>>, bool> FormsKGroups = combo =>  {
            var groups = mines.Select(mine => new List<Mine>() { mine })
                              .ToList();
            foreach(var move in combo)
            {
                int start = mines.IndexOf(move.Item1), 
                      end = mines.IndexOf(move.Item2);
                groups[end].Add(mines[start]);
                groups[start].Remove(mines[start]);
            }
            return groups.Count(g => g.Count > 0) == K;            
        };

        // Get all move combinations that form K groups
        var moveCombos = mines.SelectMany(m => mines, (m1, m2) => Tuple.Create(m1, m2))
                              .Where(tuple => !tuple.Item1.Equals(tuple.Item2)) // we have all 2^N ordered pairs of mines
                              .Combinations(N - K) // all combinations of length (N - K) of those pairs
                              .Where(x => true); // that form K groups

        // helper function for calculating the cost of a sequence of moves
        Func<IEnumerable<Tuple<Mine,Mine>>, int> MovesCost = (moves) => 
            moves.Aggregate(0, (sum, move) => 
                sum + Math.Abs(move.Item1.Distance - move.Item2.Distance) * move.Item1.Gold);

        // calculate min cost and print result
        int mincost = moveCombos.Min(MovesCost);
        Console.WriteLine(mincost);
    }
}