A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It's known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.
The first line contains a pair of integer numbers *n* and *v* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>; 1 ≤ *v* ≤ 10<sup class="upper-index">9</sup>), where *n* is the number of waterborne vehicles in the boat depot, and *v* is the truck body volume of the lorry in cubic metres. The following *n* lines contain the information about the waterborne vehicles, that is a pair of numbers *t*<sub class="lower-index">*i*</sub>, *p*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2; 1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">4</sup>), where *t*<sub class="lower-index">*i*</sub> is the vehicle type (1 – a kayak, 2 – a catamaran), and *p*<sub class="lower-index">*i*</sub> is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.
import operator
class boat:
  def __init__(self, volume, capacity):
    self.volume = volume
    self.capacity = capacity

def main():
  numberOfBoats, loryVolume = map(int, input().split())
  kayaks = []
  catamarans = []
  allInitialBoats = []
  #get the input and dived all boats into 2 categories based on their volume
  for _ in range(numberOfBoats):
    volume, capacity = map(int, input().split())
    allInitialBoats.append(boat(volume,capacity))
    if volume == 1:
      kayaks.append(capacity)
    else:
      catamarans.append(capacity)
  
  #sort kayaks in deacreasing order of their capacity
  kayaks.sort(reverse=True)
  #know we will group each 2 kayaks into a catamaran
  catamaransFromKayaks = []

  for i in range(0,len(kayaks),2):
    catamaransFromKayaks.append(kayaks[i]+kayaks[i+1])

  #know we want to sort all boats (which we made by combining kayaks to form catamarans
  #all initial catamarans and all remaining ungrouped kayaks)
  allBoats= []
  for catamaran in catamarans:
    allBoats.append(boat(2,catamaran))
  for mutants in catamaransFromKayaks:
    allBoats.append(boat(2,mutants))
  #this means that we can't group all kayaks to form catamarans and we will remain with one(last) kayak
  if len(kayaks)%2 != 0:
    allBoats.append(boat(1,kayaks[len(kayaks)-1]))
  #know it's time for sorting :)
  allBoats.sort(key=operator.attrgetter('capacity'), reverse=True)

  #know, having the boats ordered we can fill the Lory with them
  i = 0
  totalCapacity = 0
  while loryVolume > 0:
    loryVolume -= allBoats[i].volume
    totalCapacity += allBoats[i].capacity
    i += 1
  #know we want to find the order of the boats in the Lory
  #i-1 is the last boat which is in the Lory
  listOfIndexes = []
  while i > 0:
    catamaran = False
    i -= 1 #we do this first in order to start if position i - 1 which is the last boat in the Lory
    if allBoats[i].volume == 1:#this means that the last boat in the Lory is a kayak
      for index in range(len(allInitialBoats)):
        if allInitialBoats[index].volume == 1 and allInitialBoats[index].capacity == allBoats[i].capacity:
          listOfIndexes.append(index + 1)# +1 because we want to print indexes starting from 1 not from 0
          break
    else:#if their volume is 2 we have 2 cases, it's either a catamaran or there are 2 combined kayaks
      #first we check if we have such a katamaran with such capacity, if yes than it is, if no, there are 2 kayaks
      for index in range(len(allInitialBoats)):
        if allInitialBoats[index].volume == 2 and allInitialBoats[index].capacity == allBoats[i].capacity:
          listOfIndexes.append(index + 1)
          catamaran = True
          break
      if not catamaran:
        for index in range(len(catamaransFromKayaks)):
          if catamaransFromKayaks[index] == allBoats[i].capacity:
            #here we have 2 cases if index is 0 or 1 then we have 0,1 or 2,3 respectively
            #but for the second case if index > 1 we have for example for 2: 3,4; for 3: 5,6 etc.
            #in this way we find the indexes in the kayaks list, but we need the indexes in initial list
            kayakIndex1 = 2* index
            if index == 0 or index == 1:
              kayakIndex2 = kayakIndex1 + 1
            else:
              kayakIndex2 = kayakIndex1 - 1
              break
        #knowing the capacity of the kayaks we find them in the initial list
        for index in range(len(allInitialBoats)):
          if allInitialBoats[index].volume == 1 and (allInitialBoats[index].capacity == kayaks[kayakIndex1] or allInitialBoats[index] == kayaks[kayakIndex2]):
            listOfIndexes.append(index + 1)
  print(totalCapacity)
  print(*listOfIndexes)
main()