군산스탬프투어 2

문제

비버고등학교 학생들이 군산으로 수학여행을 가서 스탬프투어에 참여한다. 군산에는 관광지가 n곳 있고, 관광지마다 고유 번호가 있다. 학생은 그중에서 선생님이 정해준 수 m곳을 골라 관람하고 스탬프를 받아야 기념품을 받는다.

• i번 관광지에서 스탬프를 받으려면 그곳에서 a_i분 동안 관람해야 한다.
• 숙소에서 출발해서 관광지들을 돌고 다시 숙소로 돌아와야 한다.
• 한 장소에서 다른 장소로 이동할 때는 5분이 걸린다. (숙소→관광지, 관광지→관광지, 관광지→숙소 모두 5분)
• 이동과 관람에 쓴 시간의 합이 스탬프투어 시간 t분을 넘으면 안 된다.

기념품을 받을 수 있는 관광지 관람 순서는 모두 몇 가지인지 구해 보자. 방문하는 관광지가 같아도 순서가 다르면 다른 경우로 센다.

예시

입력

4 2 100
20 30 20 10

출력

12

출처: SFPC 2023 도전 B2 (biko.kr 1632)