크리스마스 선물

면접 대비

시간 제한1초메모리 제한128 MB

요약

가격 합이 p를 넘지 않도록 아이들을 고르고, 뽑힌 아이의 흥분도 합에서 뽑히지 않은 아이의 좌절도 합을 뺀 값을 최대로 하며, 그런 선택 중 0/1 문자열이 사전순으로 가장 작은 것을 출력한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

이 동네의 산타클로스에게 도움이 필요합니다. 이제는 모든 아이에게 선물을 줄 형편이 되지 않아, 누구에게 선물을 줄지 골라야 합니다. 산타는 각 아이마다 두 가지 값을 기록해 두었습니다. 선물을 받았을 때의 기쁨(excitement)과, 선물을 받지 못했을 때의 실망(frustration)입니다.

산타는 예산을 넘기지 않으면서 전체 만족도를 최대로 만들고 싶어 합니다. 전체 만족도는 선물을 받은 아이들의 기쁨 값을 모두 더한 뒤, 선물을 받지 못한 아이들의 실망 값을 모두 뺀 값입니다.

입력

첫째 줄에 두 정수 $n$ 과 $p$ 가 주어집니다. $n$ 은 아이의 수( $n \le 1000$ ), $p$ 는 지출 한도( $p \le 1000$ )입니다.

다음 $n$ 개의 줄에는 각 아이의 정보가 세 개의 음이 아닌 정수로 주어집니다: 가격(price), 기쁨 수치(excitement), 실망 수치(frustration). 선물을 준 아이들의 가격 합은 $p$ 를 넘을 수 없습니다.

출력

첫째 줄에 얻을 수 있는 최대 전체 만족도를 출력합니다.

둘째 줄에는 길이가 $n$ 인 0과 1로 이루어진 문자열을 출력합니다. $i$ 번째 문자가 1이면 $i$ 번째 아이가 선물을 받는다는 뜻이고, 0이면 받지 못한다는 뜻입니다. 최대 만족도를 이루는 선택이 여러 가지라면, 그중 사전순으로 가장 앞서는 문자열을 출력합니다(앞쪽 자리에 0이 오는 문자열이 더 앞섭니다).

예제5

예제 1

입력

예상 출력

11
11001

예제 2
입력
```
1 5
3 10 2
```
예상 출력
```
10
1
```
예제 3
입력
```
1 5
8 10 3
```
예상 출력
```
-3
0
```
예제 4
입력
```
2 0
0 5 1
2 3 4
```
예상 출력
```
1
10
```
예제 5
입력
```
2 1
1 1 0
1 1 0
```
예상 출력
```
1
01
```