불러오는 중
전북에는 김제 백구포도, 군산 박대, 고창 복분자, 순창 고추장, 임실 치즈, 장수 한우 등 많은 특산물이 있다. 이 중 서로 다른 3개의 특산물을 골라 나만의 선물세트를 만들어 친구 m명 모두에게 같은 세트를 하나씩 선물하려고 한다.
특산물의 가짓수 n과 각 특산물의 가격, 친구의 수 m, 특산물 구입에 쓸 수 있는 금액 k가 주어질 때, 선물세트를 만들 수 있는 방법의 수를 계산해 보자. 금액은 남아도 되고, 고른 특산물의 순서는 따지지 않는다.
첫 번째 줄에 특산물의 가짓수 n이 주어진다.
두 번째 줄에 각 특산물의 1개당 가격 p_i가 스페이스를 사이에 두고 한 줄로 주어진다.
세 번째 줄에 친구들의 인원수 m과 총 금액 k가 스페이스를 사이에 두고 주어진다.
선물세트를 만들 수 있는 방법의 수를 출력한다.
입력
5
1000 1500 300 200 700
5 25000
출력
10
세트 하나의 가격이 5,000원 이하면 5명에게 줄 수 있다. 5개 중 3개를 고르는 10가지 조합 모두 가격 합이 5,000원 이하라서 답은 10이다.
출처: SFPC 2023 준비 E1 (biko.kr 1627)