마을에는 N 명의 주민이 있으며 1에서 N까지 번호가 매겨져 있다. 거주자 i (1 ≤ i ≤ N)는 좌표 X_i에 살고 있으며 그 영향력은 E_i이다.

같은 좌표에 여러 거주자가 살고 있는 경우도 있으며, 영향력이 높은 거주자 일수록 홍보 효과가 큰 반면, 책을 사는 데 신중하다.

정올씨는 정보 과학의 책을 출판했다. 많은 사람들이 책을 사게 하기 위해 몇몇 거주자에게 책을 무료로 기부하려고 한다.

주민 i (1≤i≤N)에게 책을 기부했을 경우, 주민 i는 정올씨의 책을 갖게 된다.

책을 받지 못한 거주자 중 다음 조건을 충족시키는 모든 거주자 j (1 ≤ j ≤ N)는 정올씨의 책을 구매한다.

마을의 모든 거주자에게 정올씨의 책이 읽혀지면 정보 올림픽의 지명도가 크게 향상된다.

마을의 모든 주민이 정올씨의 책을 읽게 하기 위해 최소한 몇 명에게 기부해야 하는지 알아내자.

광고2 (Advertisement 2) timer 2초 memory 1024MB

광고2 (Advertisement 2) 2초 1024MB