import java.util.*;

public class greetings_font
{
   public static void main(String[] args)
   {
      new greetings_font(new Scanner(System.in));
   }

   // Tests if element i is in set mask
   boolean in(int i, int mask)
   {
      return ((1<<i)&mask) > 0;
   }

   public greetings_font(Scanner in)
   {
      int N = in.nextInt();
      int K = in.nextInt();
   
      Card[] vs = new Card[N];
      for (int i=0; i<N; i++)
         vs[i] = new Card(in.nextInt(), in.nextInt(), in.nextInt());
   
      TreeSet<Integer> widths = new TreeSet<>();    
      TreeSet<Integer> heights = new TreeSet<>();    
      for (Card v : vs)
      {
         widths.add(v.w);
         heights.add(v.h);
      }

      int M = 0;
      Envelope[] es = new Envelope[widths.size() * heights.size()];
      for (int w : widths) for (int h : heights)
         es[M++] = new Envelope(w, h);
 
      // Table of the cheapest envelope cost to cover this mask
      long[] cheapest = new long[1<<N];
      Arrays.fill(cheapest, Long.MAX_VALUE);
      for (Envelope e : es)
      {
         for (int mask=0; mask<1<<N; mask++)
         {
            long cost = 0;
            boolean canCover = true;
            for (int i=0; i<N; i++) if (in(i, mask))
            {
               canCover &= e.canFit(vs[i]);
               if (!canCover) break;
               cost += e.calcCost(vs[i]);
            }

            if (canCover)
               cheapest[mask] = Math.min(cheapest[mask], cost);
         }
      }

      // Find the min cost to cover these cards
      long[] dp = new long[1<<N];
      Arrays.fill(dp, Long.MAX_VALUE);
      dp[0] = 0;

      for (int k=0; k<K; k++) for (int mask=(1<<N)-1; mask>=0; mask--)
      {
         if (dp[mask] == Long.MAX_VALUE) continue;
         int cmask = ((1<<N)-1) ^ mask;
         for (int ss=cmask; ss>0; ss=(ss-1)&cmask) if (cheapest[ss] < Long.MAX_VALUE)
            dp[mask | ss] = Math.min(dp[mask | ss], dp[mask] + cheapest[ss]);
      }

      System.out.println(dp[(1<<N)-1]);
   }
}

class Envelope
{
   int w, h;

   Envelope(int ww, int hh)
   {
      w=ww; h=hh; 
   }

   boolean canFit(Card rhs)
   {
      return rhs.w <= w && rhs.h <= h;
   }

   long calcCost(Card cc)
   {
      long a1 = cc.w*cc.h;
      long a2 = w*h;
      return (a2-a1) * cc.q;
   }
}

class Card
{
   int w, h, q;
   Card(int ww, int hh, int qq)
   {
      w=ww; h=hh; q=qq;
   }
}