총기 밀수
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
돈이 매우 많은 부자 정민이는 자신이 가진 많은 돈을 지키기 위해 총을 많이 구매해 두기로 했다. 총기 소지가 불법인 한국에서는 정상적으로 총기를 구매할 수 없기 때문에, 정민이는 유능한 총기 밀수업자 경근이에게 총기 밀수를 의뢰하기로 했다.
경근이는 총 N일 동안 총기를 제공해 줄 수 있음을 공언했다. 각 날마다 총기를 밀수하는 데에는 외부적인 요인에 따라 난이도가 다를 수 있기에, 밀수해줄 수 있는 총기의 수와 총기 당 비용이 달라질 수 있다. 이에 경근이는 i번째 날에 제공 가능한 총기의 수가 총 k_i개이며, 난이도에 따라 밀수하는 비용을 결정하는 두 개의 상수 a_i, b_i가 있음을 정민이에게 알려주었다. 하루에 밀수해야 하는 양이 늘어나면 늘어날수록 밀수의 난이도는 높아지기 때문에, 더 많은 총기를 제공해야 하는 경우 a_i, b_i에 따라 총기당 가격이 올라간다. 정확히 말해서, i번째 날에 x (\le k_i)개의 총기를 밀수해야 한다면 총기 하나당 밀수하는 데 드는 가격이 a_i x + b_i원이 되어, 총 x (a_i x + b_i)의 비용을 들여야 x개의 총기를 밀수해줄 수 있다.
정민이는 이 일에 최대 C원을 투자할 것이며, 최대한 많은 총기를 사고 싶어 한다. 경근이가 알려준 정보에 따라 최적의 구매 전략을 정할 때, 구매할 수 있는 총기의 개수는 최대 몇 개일까?
입력
첫 번째 줄에 두 정수 N, C (1 \le N \le 10^5, 1 \le C \le 2 \times 10^{18})가 공백으로 구분되어 주어진다. 다음 N개의 줄의 i번째 줄에는 세 양의 정수 k_i, a_i, b_i (1 \le k_i (a_i k_i + b_i) \le 2 \times 10^{18})가 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 최대 C원을 투자하여 구매할 수 있는 총기 개수의 최댓값을 출력한다.
예제 입력
Example 1 2 11 3 2 1 2 1 2 Example 2 2 11 3 2 1 1 1 2
예제 출력
Example 1 3 Example 2 2
노트
예제 입출력에서 Example로 시작하는 줄은 실제 입출력에 포함되지 않습니다. 각각을 하나의 입출력 세트로 읽어주세요.
첫 번째 예제는 첫 번째 날에 한 개(3원), 두 번째 날에 두 개(8원)을 밀수하도록 지시하는 것이 최대한 많이 총기를 구매하는 방법이다.
두 번째 예제는 첫 번째 예제에 비해 두 번째 날에 밀수할 수 있는 총기의 개수가 하나 줄었다. 그러므로 첫 번째 날에 두 개를 밀수하거나(10원), 두 날 모두 한 개씩을 밀수하는 수(6원) 밖에 없다.