module mymodule
  implicit none
  public
  type store_type
    integer(8) :: price, storage
  end type store_type
end module mymodule

program main
  use mymodule
  implicit none
  integer(8) :: n, m, i, cost
  type(store_type), allocatable :: stores(:)

  read (*, *) n, m
  allocate (stores(n))
  do i = 1, n
    read (*, *) stores(i) % price, stores(i) % storage
  end do

  call quicksort(stores)

  cost = 0
  do i = 1, n
    if (m <= stores(i) % storage) then
      cost = cost + m * stores(i) % price
      exit
    end if
    cost = cost + stores(i) % storage * stores(i) % price
    m = m - stores(i) % storage
  end do

  write (*, "(i0)") cost

  contains

  recursive subroutine quicksort(a)
    type(store_type), intent(inout) :: a(:)
    type(store_type) :: pivot, tmp
    integer :: i, j, k, n
    real(4) :: r
    n = size(a)
    if (n <= 1) return
    i = 1
    j = n
    call random_number(r)
    k = 1 + floor(r * n)
    k = max(1, min(k, n))
    pivot = a(k)
    do
      do while (pivot % price > a(i) % price)  ! Derived type comparison
        i = i + 1
      end do
      do while (a(j) % price > pivot % price)  ! Derived type comparison
        j = j - 1
      end do
      if (i >= j) exit
      tmp = a(i)
      a(i) = a(j)
      a(j) = tmp
      i = i + 1
      j = j - 1
    end do
    call quicksort(a(1:i - 1))
    call quicksort(a(j + 1:n))
  end subroutine quicksort
end program main
