Problem: You have a playlist consisting of n songs. The i-th song is characterized by two numbers t_i and b_i — its length and beauty respectively. The pleasure of listening to set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of 3 songs having lengths [5, 7, 4] and beauty values [11, 14, 6] is equal to (5 + 7 + 4) ⋅ 6 = 96.

You need to choose at most k songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 3 ⋅ 10^5) – the number of songs in the playlist and the maximum number of songs you can choose, respectively.

Each of the next n lines contains two integers t_i and b_i (1 ≤ t_i, b_i ≤ 10^6) — the length and beauty of i-th song.

Output

Print one integer — the maximum pleasure you can get.

Examples

Input


4 3
4 7
15 1
3 6
6 8


Output


78


Input


5 3
12 31
112 4
100 100
13 55
55 50


Output


10000

Note

In the first test case we can choose songs {1, 3, 4}, so the total pleasure is (4 + 3 + 6) ⋅ 6 = 78.

In the second test case we can choose song 3. The total pleasure will be equal to 100 ⋅ 100 = 10000.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.io.FileWriter; 

// Solution

public class Main 
{    
  public static void main (String[] argv) 
  {
	  new Main();
  } 
     
  
  boolean test = true;  
  
  final int MOD = 1000000007;  
  
  
  public Main()  {
	FastReader in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
	
     
   // FastReader in = new FastReader(new BufferedReader(new FileReader("Main.in")));   
    
    //int nt = in.nextInt();    
    int nt = 1;
    //StringBuilder sb = new StringBuilder();
    
    
    for (int it = 0; it < nt; it++) 
    {
       int n = in.nextInt();
     
       int k = in.nextInt();
     
       int[][] songs = new int[n][2];
       for (int i = 0; i < n; i++)
       {
           songs[i][0] = in.nextInt();
           songs[i][1] = in.nextInt();           
       }
       
       // sort by beauty, from large to small
       Arrays.sort(songs, (x,y)->(Integer.compare(y[1], x[1])));
       long len = 0;
       long maxPleasure = 0;
       PriorityQueue<Integer> pq = new PriorityQueue<>(k);
       for (int i = 0; i < k; i++) 
       {
           len += songs[i][0];           
           pq.offer(songs[i][0]);
           maxPleasure = Math.max(maxPleasure, len * songs[i][1]);
       }
       
       
       for (int i = k; i < n; i++)
       {
           pq.offer(songs[i][0]);
           len -= pq.poll();
           len += songs[i][0];
           maxPleasure = Math.max(maxPleasure, len * songs[i][1]);
       }
       System.out.println(maxPleasure);
       //System.out.print(sb);
    }
    //System.out.print(sb);
  }
  
  
  private List<Integer> getMinFactor(int sum)
  {
      List<Integer>  factors = new ArrayList<>();
      
               for (int sz = 2; sz <= sum / sz; sz++){
                   if (sum % sz == 0) {
                       factors.add(sz);
                       factors.add(sum / sz);
                   }
               }
               if (factors.size() == 0)
                   factors.add(sum);
          
      return factors;
  }
  
  /* Tree class */
  class Tree {
      int V = 0;
      int root = 0;
      List<Integer>[] nbs;
      int[][] timeRange;
      int[] subTreeSize;
      int t;
      boolean dump = false;
      
      public Tree(int V, int root)
      {
          if (dump) 
              System.out.println("build tree with size = " + V + ", root = " + root); 
          
          this.V = V;          
          this.root = root;
          nbs = new List[V];
          subTreeSize = new int[V];
          for (int i = 0; i < V; i++)
              nbs[i] = new ArrayList<>();
          
              
      }
      
      public void doneInput()
      {
          dfsEuler();
      }
      
      public void addEdge(int p, int q)
      {
          nbs[p].add(q);
          nbs[q].add(p);
      }
      
      private void dfsEuler()
      {
          timeRange = new int[V][2];          
          t = 1;
          dfs(root);           
      }
      
      private void dfs(int node)
      {
          if (dump)
              System.out.println("dfs on node " + node + ", at time " + t);
          timeRange[node][0] = t;
          
          for (int next : nbs[node]) {
              if (timeRange[next][0] == 0)
              {
                  ++t;
                  dfs(next);                  
              }
          }
          timeRange[node][1] = t;
          subTreeSize[node] = t - timeRange[node][0] + 1;
      }
      
      public List<Integer> getNeighbors(int p) {
          return nbs[p];
      }
      
      public int[] getSubTreeSize(){
          return subTreeSize;
      }
      
      public int[][] getTimeRange()
      {
          if (dump){
              for (int i = 0; i < V; i++){
                  System.out.println(i + ": " + timeRange[i][0] + " - " + timeRange[i][1]);
              }
          }
          return timeRange;
      }
      
  }
  
  /* segment tree */
  class SegTree {
      long[] tree;
      long[] lazy;
      int n;
      boolean dump = false;
      
      public SegTree(int n)
      {
          if (dump)
              System.out.println("create segTree with size " + n);
          this.n = n;
          tree = new long[n*4];
          lazy = new long[n*4];
      }
      
      public SegTree(int n, int[] a) {
          this(n);
          buildTree(1, 0, n-1, a);
      }
      
      private void buildTree(int node, int lo, int hi, int[] a)
      {
          if (lo == hi) {
              tree[node] = a[lo];
              return;
          }
          
          int m = (lo + hi) / 2;
          buildTree(node * 2, lo, m, a);
          buildTree(node * 2 + 1, m + 1, hi, a);
          pushUp(node, lo, hi);
      }
      
      
      private void pushUp(int node, int lo, int hi)
      {
          if (lo >= hi) return;
          
          // add combine fcn
      }
      
      private void pushDown(int node, int lo, int hi)
      {
          if (lo > hi || lazy[node] == 0) return;
          
          tree[node] += lazy[node];
          tree[node] %= MOD;
          
          if (lo < hi) {              
              lazy[node * 2] += lazy[node];
              lazy[node * 2 + 1] += lazy[node];
              lazy[node * 2] %= MOD;
              lazy[node * 2 + 1] %= MOD;
          }
          
          lazy[node] = 0;
      }
      
      public void rangeUpdate(int fr, int to, long val)
      {
          if (dump)
              System.out.println("rangeUpdate : " + fr + " - " + to + " delta = " + val);
          rangeUpdate(1, 0, n-1, fr, to, val);
      }
      
      public long pointQuery(int p)
      {
          return pointQuery(1, 0, n-1, p);
      }
      
      
      private void rangeUpdate(int node, int lo, int hi, int fr, int to, long val)
      {
          if (dump)
              System.out.println("rangeUpdate : " + node + "[" + lo + " - " + hi + "]" + fr + " - " + to + " delta = " + val);
          
          pushDown(node, lo, hi);
          
          if (lo == fr && hi == to) {
              lazy[node] = val;              
              return;
          }
          
          int m = (lo + hi) / 2;
          if (to <=  m) 
              rangeUpdate(node * 2 , lo, m, fr, to, val);
          else if (fr > m)
              rangeUpdate(node * 2 + 1, m + 1, hi, fr, to, val);
          else {
              rangeUpdate(node * 2, lo, m, fr, m, val);
              rangeUpdate(node * 2 + 1, m + 1, hi, m + 1, to, val);
          }
          
          pushUp(node, lo, hi);          
      }
  
      /* pre-condition: lo <= p <= hi */
      private long pointQuery(int node, int lo, int hi, int p)
      {
          pushDown(node, lo, hi);
          
          if (lo == hi)
          {
              return tree[node];
          }
          
          int m = (lo + hi) / 2;
          if (p <= m) 
              return pointQuery(node * 2, lo, m, p);
          else
              return pointQuery(node * 2 + 1, m + 1, hi, p);
      }      
  
  }
  
  
  private long inv(long v)
  {
      return pow(v, MOD-2);
  }
  
  private long pow(long v, int p)
  {
      long ans = 1;
      while (p > 0)
      {
          if (p % 2 == 1)
              ans = ans * v % MOD;
          v = v * v % MOD;
          p = p / 2;
      }
      return ans;
  }
  
  private double dist(double x, double y, double xx, double yy)
  {
      return Math.sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
  }
  

  
 
  private int mod_add(int a, int b) {
      int v = a + b;
      if (v >= MOD) v -= MOD;
      return v;
  }
  
  
  private long overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
      if (x1 > x3) return overlap(x3, y3, x4, y4, x1, y1, x2, y2);
      
      if (x3 > x2 || y4 < y1 || y3 > y2) return 0L;
      
      //(x3, ?, x2, ?)
      int yL = Math.max(y1, y3);
      int yH = Math.min(y2, y4); 
      int xH = Math.min(x2, x4);
      
      return f(x3, yL, xH, yH);
  }
  //return #black cells in rectangle
  private long f(int x1, int y1, int x2, int y2) {
      long dx = 1L + x2 - x1;
      long dy = 1L + y2 - y1;
      if (dx % 2 == 0 || dy % 2 == 0 || (x1 + y1) % 2 == 0) 
          return 1L * dx * dy / 2;
      return 1L * dx * dy / 2 + 1;
  }
  
  private int distM(int x, int y, int xx, int yy) {
      return abs(x - xx) + abs(y - yy);
  }
  
  private boolean less(int x, int y, int xx, int yy) {
      return x < xx || y > yy;
  }
  
  private int mul(int x, int y) {
      return (int)(1L * x * y % MOD);
  }
  
  
 
  
  private int nBit1(int v) {
      int v0 = v;
      int c = 0;
      while (v != 0) {
          ++c;
          v = v & (v - 1);
      }
      return c;
  }
  
  private long abs(long v) {
      return v > 0 ? v : -v;
  }
  
  private int abs(int v) {
      return v > 0 ? v : -v;
  }
  
  private int common(int v) {
      int c = 0;
      while (v != 1) {
          v = (v >>> 1);
          ++c;
      }
      
      return c;
  }
  
  private void reverse(char[] a, int i, int j) {
      while (i < j) {
          swap(a, i++, j--);
      }
  }
  
  private void swap(char[] a, int i, int j) {
      char t = a[i];
      a[i] = a[j];
      a[j] = t;
  }
  
  private int gcd(int x, int y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private long gcd(long x, long y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private int max(int a, int b) {
      return a >  b ? a : b;
  }
  
  private long max(long a, long b) {
      return a >  b ? a : b;
  }
  
  private int min(int a, int b) {
      return a >  b ? b : a;
  }
  
  private long min(long a, long b) {
      return a >  b ? b : a;
  }
  
  static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader(BufferedReader in)
        {            
            br = in;
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    String line = br.readLine();
                    if (line == null || line.length() == 0) return "";
                    st = new StringTokenizer(line);
                }
                catch (IOException  e)
                {
                    return "";
                    //e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                return null;
                //e.printStackTrace();
            }
            return str;
        }
    }
}