5896번 - 효율적으로 소 사기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1305 | 294 | 205 | 25.721% |
문제
농부 존은 새 소들이 필요하다! 그래서 농부 존은 소 시장에 가서 새 소들을 사려고 한다.
농부 존은 돈이 많이 없기 때문에 소들을 최대한 효율적으로 사야 한다. 그래서 농부 존은 M원과 K개의 소 쿠폰을 가지고 소 시장에 나온 N마리의 소들을 최대한 많이 사려고 한다.
소 쿠폰은 소 한 마리당 한 번만 쓸 수 있고, 쓰고 나면 사라진다. i번째 소는 Pi원이고, 쿠폰을 썼을 때는 Ci원이 될 때, 농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.
입력
첫 번째 줄에 소 시장에 나온 소들의 마릿수 N(1 ≤ N ≤ 50,000), 농부 존이 가지고 있는 쿠폰의 개수 K(1 ≤ K ≤ N), 농부 존이 가지고 있는 돈 M(1 ≤ M ≤ 1014)이 주어진다.
다음 줄부터 Pi (1 ≤ Pi ≤ 109), Ci (1 ≤ Ci ≤ Pi)가 주어진다.
출력
농부 존이 최대로 살 수 있는 소 마릿수를 출력하라.
예제 입력 1
4 1 7 3 2 2 2 8 1 4 3
예제 출력 1
3
힌트
농부 존은 1개의 쿠폰과 7원을 가지고 소 시장에 갔다.
3번째 소에 쿠폰 하나를 쓰고 1,2,3번 소를 산다. (1 + 2 + 3 = 6원)
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호