Summary of JD internship written examination questions

One 、 The most valuable entrustment information

I can't remember the details of the title , I can only give a general description of , It's to seek the most valuable entrustment information .
n、s、B、S among n Delegate information ,s The number of the most valuable delegation information required ,B On behalf of buying 、S Represents the sale of ,S Sell from small to large , Buy from big to small .
Output ：

6 2B 50 2 S 50 1 S 20 2 S 30 1 B 40 4 B 50 6 

Output ：

B 50 8B 40 4S 20 2S 30 1

（ remarks ：6 Represents the number of entrustment information 、2 The representative said that the buying and selling entrustment information were returned respectively 2 individual , Each line is like “B 50 2", First field B On behalf of buying ,S Represents the sale of ,50 On behalf of price , The last field represents quantity ）

Two 、 Programming questions 2

3、 ... and 、 Election game

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description:
Xiao Dong and other children are playing a game about election . Elections are held by voting , The person who gets the most votes will win .
Xiaodong is numbered 1 The candidate for , In addition, there are other candidates to participate in the election . According to the preliminary investigation , All the children who are going to vote have a certain voting preference , If Xiaodong wants to win , We must fight for some children who are ready to vote for other candidates . Because the resources of Xiaodong are relatively limited , She hopes to win with the least cost , Please help calculate the minimum number of votes she needs to win .

Input

There are several groups of inputs , Each group contains two lines , The first line is a positive integer n（2<=n<=100）, Indicates the number of candidates , The second line is the number of votes each candidate is expected to get , Separate... By spaces , The expected number of votes per person is 1 To 1000 Between （ contain 1 and 1000）. After Xiaodong's fight , The number of possible candidates is 0 Or exceed 1000 The situation of .

Output

For each group of test data , Output a single line , The content is the minimum number of votes Xiaodong needs to win .

The sample input

55 1 11 2 841 8 8 827 6

Sample output

460​

Four 、 a birthday present

5、 ... and 、 Divide candy

A candy company specializes in producing children's candy , Its most popular candies for children are A1、A2 Two sequences , All are packed in boxes . Packed A1 Candy like volume is a storage unit , And packaged A2 The volume of candies is just A1 Twice the class .

The reason why these two kinds of candy are popular with children , It's because candy contains magic factors developed exclusively by the company .A1 or A2 Candy in the sequence , It seems that the packaging may be the same , But because of the different magic factor content, it is subdivided into different products .

Approaching traditional festivals , The company's candy is in short supply . As a smart candy distributor , Xiaodong hopes to make a lot of money with this , So I took cash and drove a truck to the company to pick up the goods . The capacity of the truck is certain , Xiaodong hopes that the candy purchased can be as full as possible , And the total content of magic factors in candy is the highest . As long as the truck capacity is not exceeded , Candy can always be loaded into the truck .

Xiao Dong hopes you can help her solve this problem .

Input

There are multiple sets of test data in the input . The first row of each set of test data has two integers n and v,1<=n<=10^5,
1<=v<=10^9,n For the number of candies available ,v Is the capacity of the truck . And then n Specific information about behavioral candy , The first line is numbered 1, The second line is numbered 2, And so on , The last line is numbered n. Each line contains two integers ti and pi,1<=ti<=2,
1<=pi<=10^4,ti It is the sequence of candy ,1 by A1、2 by A2,pi Is the magic factor content .

Output

For each group of test data , First, output the highest content of magic factor in the candy that can be purchased in a separate line , Then, the candy numbers separated by spaces are output in the order of number from small to large in a separate line , If there are multiple groups of candy combinations that can meet the requirements , Output the group with the lowest number . If no candy can meet the requirements , Then output... In the first line 0, The second line outputs “No”.

The sample input

3 21 22 71 3

Sample output

72