Maximizing Expo Profit

A publishing company is hosting a book expo and has n types of books in its inventory. Each book type has an associated cost c_i, popularity p_i, and a number of available units.

The company processes a sequence of q events. There are two types of events:

• Type 1: A customer buys a book of type x. If at least one unit is available, the inventory for that type decreases by one. Otherwise, the event is ignored.
• Type 2: The company needs to decide which books to display at the expo. They want to choose a subset of book types (each at most once) such that the total popularity does not exceed a given threshold P, while maximizing the total cost (profit) of the selected books. Formally, if I is the set of indices of book types that are still in stock and each book type i has cost c_i and popularity p_i, then the goal is to compute</p>

  \(f(P) = \max \{ \sum_{i \in S} c_i \;:\; S \subseteq I, \; \sum_{i \in S} p_i \le P \}\)

  for every type 2 event.

  You need to simulate these events in the given order. For each type 2 event, output the computed maximum total cost on a separate line.

  inputFormat

  The input is given from stdin and has the following format:

  n P
  c1 p1 inventory1
  c2 p2 inventory2
  ... (n lines)
  q
  event1
  event2
  ... (q lines)

  Here, the first line contains two integers n (the number of book types) and P (the popularity threshold). The next n lines each contain three integers: the cost, the popularity, and the initial number of available units for that book type. The following line contains an integer q, which is the number of events. Each of the next q lines describes an event. An event of type 1 is represented by two integers: "1 x", where x (1-indexed) is the book type being sold. An event of type 2 is represented by a single integer: "2".

  outputFormat

  For each type 2 event, print a single line to stdout containing the maximum total cost that can be obtained by selecting a subset of the available book types such that the sum of their popularities does not exceed P.

  ## sample

  3 1000
  100 150 1
  200 200 2
  150 300 1
  5
  1 1
  1 2
  2
  1 2
  2
  

  350
  150
  

  </p>