페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6075

소로 탑쌓기 1s 1024MB

문제

N (1≤N≤2⋅10^5)종류의 서로 다른 무게를 가진 소들이 있다. 각 i∈[1,N]에 대해 a_i마리의 소는 무게 w_i (1≤a_i≤10^9, 1≤w_i≤10^9)를 갖는다.

소들이 균형 잡힌 탑을 형성하려고 하는데, 탑은 각 소가 다른 소 위에 쌓여 일자로 쌓인 형태이다. 탑의 균형을 맞추기 위해서는 탑에 속한 각 소의 무게가 바로 위에 있는 소의 무게보다 적어도 K (1≤K≤10^9)만큼 커야 한다. 어떤 소든 한 번에 최대 하나의 균형 잡힌 탑에 속할 수 있다.

동시에 M (1≤M≤10^9)개의 이하의 균형 잡힌 탑을 만든다면, 최대 몇 마리의 소가 탑을 구성하는데 사용되는지 알아보자.


입력

첫 번째 줄에는 세 개의 공백으로 구분된 정수 N, M, K가 주어진다.

다음 N 줄에는 두 개의 공백으로 구분된 정수 w_i와 a_i가 있습니다. 모든 w_i가 서로 다름이 보장된다.


출력

소들이 최적으로 탑을 형성한다면 균형 잡힌 탑을 구성할 수 있는 소의 최대 수를 출력한다.


예제 #1

3 5 2
9 4
7 6
5 5
14

FJ는 무게가 5, 7 및 9인 소로 네 개의 균형 잡힌 탑을 만들 수 있고, 무게가 5 및 7인 소로 하나의 균형 잡힌 탑을 만들 수 있습니다.


예제 #2

3 5 3
5 5
7 6
9 4
9

FJ는 무게가 5 및 9인 소로 네 개의 균형 잡힌 탑을 만들 수 있으며, 무게가 7인 소로 하나의 균형 잡힌 탑을 만들 수 있습니다. 또는 무게가 5 및 9인 소로 네 개의 균형 잡힌 탑을 만들 수 있으며, 무게가 5인 소로 하나의 균형 잡힌 탑을 만들 수도 있습니다.



출처

USACO 2023 December Silver

로그인해야 코드를 작성할 수 있어요.