프라이버시 손실

정부가 시민을 감시해도 되는지를 두고 벌어지는 윤리 논쟁의 한가운데에는 "프라이버시"가 지킬 만한 가치가 있느냐는 물음이 있다. 여기서 다루는 것은 현행법이 정부에게 그럴 권한을 주었느냐를 따지는 법률 논쟁이 아니다. 감시를 옹호하는 쪽은 프라이버시를 원하는 사람은 불법을 저지르려는 사람뿐이라고 말하곤 한다. 하지만 닫힌 문 뒤에서 무엇을 하느냐고 아주 사적인 질문을 던지면 그런 주장을 펴던 사람도 금세 발을 뺀다. 실제로 프라이버시의 상당 부분은 불법은 아니지만 남들이 곱게 보지 않을 수 있어서 알리고 싶지 않은 행동을 지키는 문제다. 예를 들어 가장 진심을 담아 쓴 연애편지가 널리 퍼지거나, 고된 하루 끝에 소파에서 침을 흘리며 뻗어 있는 사진이 돌아다니면 대부분은 몹시 창피할 것이다.

문제는 보안을 명분으로 제안하는 방법 대부분이 보안 이득과 함께 프라이버시 비용, 그리고 돈이나 노력의 비용을 같이 치른다는 점이다. 모든 집과 아파트의 방마다 카메라를 달고 영상을 분석하면 범죄와 테러를 얼마간 막을 수 있겠지만, 돈이 엄청나게 드는 데다 사람들의 프라이버시를 크게 침해한다. 오가는 이메일을 전부 들여다보는 쪽은 프라이버시 침해가 조금 덜하고 비용도 싸지만 효과도 그만큼 떨어진다. 그래서 "받아들일 만한" 조합을 설계하려면 프라이버시 손실과 금전 비용을 보안 이득과 견주어 저울질해야 한다.

여러 감시 방안이 각각 보안 이득, 프라이버시 비용, 금전 비용과 함께 주어진다. 여기에 예산과 사회가 감수할 수 있는 프라이버시 침해 총량도 주어진다. 두 제약을 모두 지키면서 얻을 수 있는 보안 이득 합의 최댓값을 구하라.

각 방안은 고르거나 고르지 않으며, 같은 방안을 두 번 고를 수는 없다.

첫 줄에 데이터 세트의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 세트가 다음 형식으로 주어진다.

각 데이터 세트의 첫 줄에는 정수 $n$, $B$, $P$가 공백으로 구분되어 주어진다. $1 \le n \le 100$은 검토하는 감시 방안의 개수, $0 \le B \le 100$은 감시에 쓸 수 있는 전체 예산, $0 \le P \le 100$은 사회가 받아들일 수 있는 프라이버시 비용의 총량이다.

그다음 $n$개의 줄에는 각각 정수 $s_i$, $c_i$, $p_i$가 주어진다. $0 \le s_i \le 1000$은 방안 $i$의 보안 이득, $0 \le c_i \le 100$은 방안 $i$의 비용, $0 \le p_i \le 100$은 방안 $i$의 프라이버시 손실이다.

각 데이터 세트마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 그 데이터 세트의 번호이고 1부터 센다. 다음 줄에는 예산과 프라이버시 제약을 모두 지키면서 얻을 수 있는 보안 이득의 최댓값을 출력한다. 데이터 세트 사이에는 빈 줄을 하나 넣고, 마지막 데이터 세트 뒤에는 빈 줄을 넣지 않는다.