Christmas Presents

Interview

Time limit1sMemory limit128 MB

Summary

Choose a subset of children whose total price is at most p, maximizing excitement of chosen minus frustration of unchosen, and output the lexicographically smallest optimal 0/1 string.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

The local Santa Claus needs your help. He can no longer afford to give every child a present, so he must decide which children receive one. For each child he has recorded two values: the child's excitement if they receive a present, and their frustration if they do not.

Santa wants to maximize the total satisfaction without letting his total spending exceed his budget. The total satisfaction is the sum of the excitement values of the children who receive a present, minus the sum of the frustration values of the children who do not.

Input

The first line contains two integers $n$ and $p$ : the number of children ( $n \le 1000$ ) and the spending limit ( $p \le 1000$ ).

Each of the next $n$ lines contains three nonnegative integers: the price, the excitement level, and the frustration level of one child. The total price of the children who receive a present must not exceed $p$ .

Output

On the first line, print the maximum total satisfaction.

On the second line, print a string of $n$ characters made of 0s and 1s: the $i$ -th character is 1 if the $i$ -th child receives a present and 0 otherwise. If several selections achieve the maximum satisfaction, print the lexicographically smallest such string (a string that has 0 in an earlier position is considered smaller).

Examples5

Example 1

Input

Expected output

11
11001

Example 2
Input
```
1 5
3 10 2
```
Expected output
```
10
1
```
Example 3
Input
```
1 5
8 10 3
```
Expected output
```
-3
0
```
Example 4
Input
```
2 0
0 5 1
2 3 4
```
Expected output
```
1
10
```
Example 5
Input
```
2 1
1 1 0
1 1 0
```
Expected output
```
1
01
```