총기 규제

지금 새로운 세대의 학생들을 거리로 이끌어 시위하게 하고, 나아가 정치 과정에 참여하도록 하는 주제는 총기 규제다. 미국인의 압도적 다수가 현 상태보다 더 엄격한 총기 규제를 지지하고, 끔찍한 총기 사망 통계3에도 불구하고, 지난 20~30년 동안 총기 관련 법은 오히려 약화되었다. 주된 이유 하나는 전미총기협회(NRA)의 지나치게 큰 영향력이다. 예전에 NRA는 대체로 총기 소유자를 대변했지만, 지금은 사실상 총기 제조사의 로비 조직이다. NRA가 펼치는 논리는 사실상 다음과 같다. (1) 수정 헌법 제2조는 절대적이며, 어떤 법도 총기 소유를 제한해서는 안 된다. (2) 특히, 우리 회원사는 범죄자와 불안정한 사람에게 총을 팔 권리가 있다. (3) 봐라, 총을 든 범죄자가 저렇게 많다! 그들로부터 자신과 가족을 지키려면 총을 잔뜩 사는 게 좋다.

NRA가 정치인에게 이렇게 큰 힘을 행사하는 이유 중 하나는, 상당수 의원(특히 거의 모든 공화당 의원)이 이미 NRA의 입장을 지지하는 상황을 만들어 놓았기 때문이다. 그래서 NRA는 이탈하는 개별 의원을 즉시 악마화 광고 공세의 표적으로 삼을 수 있다. 거의 모든 개별 의원을 낙선시킬 자원을 NRA가 가지고 있으니, 어느 개인이나 작은 연합도 감히 입장을 바꾸지 못한다. 반대로 상당수 의원이 동시에 입장을 바꾼다면, 그 수와 NRA의 공격 자원 부족 덕분에 보호받을 가능성이 크다. 안타깝게도 그런 큰 연합은 총기 규제의 많은 부분에서 합의하기 어려울 것이다. 연합의 각 의원은 타협이 필요한 작은 요구를 하나씩 가지고 있기 때문이다. 연합의 구성원 중 적어도 한 명은 낙선하지 않도록 보장되는 연합이 달성할 수 있는 최소 총 타협량을 계산해야 한다.

더 형식적으로, 각 의원마다 두 수가 주어진다. NRA가 이 의원을 낙선시키기 위해 지출해야 하는 금액과, 이 의원이 요구하는 타협량이다. 의원 집합 S가 안전하다는 것은, S의 모든 의원을 낙선시키는 데 드는 금액의 합이 NRA의 예산을 초과한다는 뜻이다. S에 요구되는 타협량은 구성원 각자의 타협량을 모두 더한 값이다. 안전한 집합이 달성할 수 있는 최소 타협량을 구해야 한다.

3상당수는 실제로 자살이다.

첫 줄에는 입력 데이터 세트의 수 K ≥ 1이 주어진다. 그다음에는 다음 형식의 데이터 세트 K개가 이어진다.

데이터 세트의 첫 줄에는 두 정수 n, B가 주어진다. 1 ≤ n ≤ 50은 의원 수이고, 0 ≤ B ≤ 1000은 NRA의 예산이다.

이어서 n개의 줄이 주어지며, 각 줄에는 음이 아닌 정수 bi, ci가 있다. bi ≤ 1001은 NRA가 의원 i를 낙선시키는 데 드는 금액이고, ci ≤ 1001은 의원 i가 요구하는 타협량이다. B < Σibi임이 보장되므로, 안전한 연합이 존재한다.

각 데이터 세트마다 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 x는 데이터 세트의 번호다. 그다음 줄에 안전한 의원 연합이 달성할 수 있는 최소 타협량을 출력한다.

각 데이터 세트 뒤에는 빈 줄을 출력한다.