컴퓨터 구매의 가치

가장 가성비 좋은 컴퓨터를 직접 조립하려고 합니다. 컴퓨터는 $T$ ($1 \le T \le 5$)가지 종류의 부품으로 이루어지며, 각 종류의 부품을 정확히 하나씩 포함해야 합니다.

각 부품은 정수 비용 $c_i$ ($1 \le c_i \le 3000$), 정수 가치 $v_i$ ($1 \le v_i \le 3000$), 종류 $t_i$ ($1 \le t_i \le T$)를 가집니다.

온라인 부품 상점에는 고를 수 있는 $N$개 ($1 \le N \le 1000$)의 부품이 있습니다.

주어진 예산 $B$ ($1 \le B \le 3000$)에 대해, 총비용이 $B$ 이하가 되도록 하면서 컴퓨터에 들어가는 부품들의 총 가치를 최대로 만드세요.

이러한 컴퓨터를 조립할 수 없다면 $-1$을 출력합니다.

첫째 줄에는 컴퓨터에 필요한 부품 종류의 수 $T$가 주어집니다.

다음 줄에는 $N$이 주어지고, 이어서 $N$개의 줄에 각각 세 정수 $c_i$, $v_i$, $t_i$가 공백 하나로 구분되어 주어집니다.

마지막 줄에는 예산 $B$가 주어집니다.

총비용이 $B$ 이하인 컴퓨터의 최대 총 가치를 출력합니다. 유효한 컴퓨터를 조립할 수 없다면 $-1$을 출력합니다.

예제에서 비용이 $11$인 부품과 비용이 $5$인 부품을 고르면 가치가 $18$인 컴퓨터가 되며, 더 높은 가치를 내는 조합은 없습니다.