네오 로빈 후드
시간 제한4초메모리 제한256 MB
돈을 훔칠 정치인 집합과 뇌물을 줄 정치인 집합을 서로 겹치지 않게 골라, 훔친 돈의 합이 뇌물의 합 이상이 되도록 하면서 훔치는 사람 수를 최대로 만든다.
문제
네버랜드에는 정치적 야망을 가진 정치인 명이 있다. 이들은 부유하지만, 정치적 영향력을 얻기에는 충분히 부유하지 않다. 네버랜드는 재정적으로 투명한 나라이므로, 우리는 각 정치인의 은행 잔고를 알고 있다. 번째 정치인()은 달러를 가지고 있고, 정치적 목표를 달성하기 위해 달러가 더 필요하다.
당신은 악명 높은 현대의 슈퍼히어로, 네오 로빈 후드다. 당신은 부자들에게서 훔쳐서 생계를 유지하며, 그 목적은... 글쎄, 당신에게 보답을 약속하는 사람을 돕기 위해서다. 명의 정치인 각각에 대해 다음 중 하나를 선택할 수 있다:
- 그의 달러를 훔친다;
- 아무것도 하지 않는다;
- 그가 정치적 영향력을 얻도록 돕는다. 즉, 그에게 달러를 준다.
하지만 당신의 봉사는 공짜가 아니다. 당신이 정치인 한 명이 정치적 영향력을 얻도록 도와주면, 그는 당신의 도둑질 중 하나를 은폐해 주어야 한다. 예를 들어 알리바이를 제공하는 방식으로. 그 대신, 당신은 미래에 그의 돈을 훔치지 않을 의무가 있다.
처음에 당신은 돈이 없다. 당신의 임무는 가능한 한 많은 정치인을 털는 것이다. 하지만 잡히면 안 되므로, 저지르는 각 범죄마다 이를 책임져 줄 정치인이 한 명 필요하다.
당신이 털 수 있는 사람의 최대 수는 얼마인가?
입력
입력의 첫 번째 줄에는 양의 정수 ()이 주어지며, 이는 정치인의 수다. 입력의 두 번째 줄에는 개의 양의 정수 (, 모든 )가 주어진다. 입력의 세 번째 줄에는 개의 양의 정수 (, 모든 )가 주어진다.
출력
당신이 훔칠 수 있는 사람의 최대 수를 나타내는 하나의 음이 아닌 정수를 출력한다.
당신은 자신의 재산을 최대화하는 것이 아니라, 훔치는 사람의 수를 최대화해야 한다는 점에 유의하라.