4584 - 장보기 (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

마트에서 장을 보려고 한다. 0~n-1 상품을 전부 사려면 최소 얼마의 금액이 필요할지 구해보자.

이전의 장보기 문제와 같으나 이번엔 묶음상품이 있다.

Input

Line 1: 필요한 상품 갯수 n (1 <= n <= 9)

Line 2: 상품갯수 N (1 <= N <= 16)

Line 3~N+2: 묶인 상품 갯수 m, 상품 종류 m개, 가격

(1 <= m <= 9, 0 <= 가격 <= 1,000,000)

항상 0~n-1을 전부 구매할 수 있는 데이터만 들어온다.

Output

Line 1: 상품 0~n-1을 전부 구매하기 위한 금액의 최솟값

Sample Input

3
5
1 0 10000
2 0 1 11000
2 2 3 10000
2 0 2 15000
1 1 10000

Sample Output

21000

Hint

3은 살 필요 없지만 0, 1, 2, 3 사는 것이 0, 1, 2만 사는 것보다 저렴하다면 구입해도 된다.