문제 1024 · 기초 4

점심 메뉴 조합

인증 제출 통계 · 5분마다 갱신 · 정답 비율 = 정답 제출 / 전체 제출
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2000ms / 테스트 (언어별 보정은 아래 표)	메모리: 측정하지 않음(브라우저 채점)	0	0	0	0.00%

문제

회사 앞 분식집 메뉴판에 메뉴 N개가 있다. i번째 메뉴의 가격은 p_i 원이고, 팀원들이 매긴 만족도는 s_i 점이다. 점심 예산 B원 안에서 메뉴를 골라 만족도 합이 가장 크게 하려 한다. 같은 메뉴는 한 번만 시킬 수 있고, 아무것도 시키지 않아도 된다. 만족도 합이 가장 큰 조합이 여럿이면 그중 가격 합이 가장 작은 조합을 고른다. 그때의 만족도 합과 가격 합을 구하라.

입력

첫째 줄에 N 과 B 가 주어진다. (1 ≤ N ≤ 15, 0 ≤ B ≤ 300,000)

다음 N개 줄에 p_i 와 s_i 가 주어진다. (100 ≤ p_i ≤ 30,000, 1 ≤ s_i ≤ 100)

출력

만족도 합과 가격 합을 공백으로 구분해 출력한다.

예제 입력 1

예제 출력 1

65 9000

예제 입력 2

2 1000
1500 10
2000 20

예제 출력 2

0 0

힌트 펼치기

메뉴가 15개 이하이므로 고르는 방법은 2^15 = 32,768가지뿐이다. 전부 확인해도 된다.
0 부터 2^N − 1 까지의 정수 mask 에서 i번째 비트가 1 이면 i번째 메뉴를 고른 것으로 보자.

풀이 작성

연습 채점은 공개 테스트로 실행합니다. 인증 제출은 코드를 봉인한 뒤 새 입력을 실행하고 서버에서 출력을 대조하며 코드와 판정을 저장합니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

연습 기록은 이 브라우저에 최근 50개를 저장합니다. 인증 기록은 내 제출에서 확인하세요.

이 브라우저의 제출 기록

언어별 제한

테스트 케이스마다 새 전역에서 실행하며 준비 시간은 제외합니다. 시간 초과된 출력은 검사하지 않습니다. 브라우저·기기 성능에 따라 실행 시간이 달라집니다.

언어	엔진(버전)	시간 제한	메모리
javascript	사용자 브라우저 JavaScript 엔진 (버전은 브라우저에 따라 다름)	2000ms / 테스트	측정하지 않음(브라우저 채점)
python	Pyodide 314.0.7 (CPython 3.14 WASM)	8000ms / 테스트	측정하지 않음(브라우저 채점)

문제

입력

출력