All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Maximize It !!!

Greedy Algorithms, Sorting


Ryan has a keen interest in collecting gems . He always urged his father to let him collect more number of gems . So , on his birthday , his father offered him a surprise gift . The gift is described as follows . 

Ryan is given a collection of N number of gems . Each gem is of a unique type and is assigned a unique number Ni (unique identity) . Each gem has a weight associated with it (may or may not be unique) . Ryan has a bag , with capacity to hold gems upto weight K grams . Bag can hold gems upto weight less than or equal to K grams .

He will use this bag to collect gems . Now , due to his keen interest in maintaining a collection of gems , he wants to collect as many distinct types of gems as possible . Now , he wants your help in selecting maximum distinct types of gems for his collection . Based on the given conditions , output those distinct gems that will be collected in given bag .

Input Format :

First Line N - total number of distinct gems present in the given collection .

Second Line K -  capacity of the given bag(in grams) .

Next N lines ...

Ni Wi - the unique number(type) Ni and weight Wi assigned to the ith gem .

Output Format :

Print the string comprising of the types(numbers) of the selected gems sorted in ascending order separated by commas i.e. with comma  ' , ' in between on a single line . If no gem can be selected , then print -1 on a single line .

Constraints :

\(1 \le N \le 10^6\)

\(1 \le K \le 10^9\)

\(1 \le N_i \le N\)

\(1 \le W_i \le 10^9\)

1 1
2 2
3 3

As per the given input , Ryan would pick gem number 1 , 2 and 3 because summation of associated weights 1->1 , 2->2 , 3->3 is equal to capacity 6 of the bag .

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications