Time Limit: 1s
Memory Limit: 128MB
가로 길이 n, 세로 길이 m인 직사각형 땅을 d일간 임대해서 작물을 기르려고 한다.
작물의 크기와 수확까지 걸리는 기간이 제각각일 때, 최대 몇 개의 작물을 수확할 수 있을지 구해보자.
이 때 작물은 회전시켜 심을 수 있다.
* Line 1 : 땅의 가로 길이 n, 땅의 세로길이 m, 땅의 임대기간 d (1 ≤ n,m,d ≤ 5)
* Line 2 : 작물 갯수 N (1 ≤ N ≤ 100)
* Line 3~N+2 : 작물 가로세로 길이 i, j, 수확까지 걸리는 기간 k (1 ≤ i,j,k ≤ 10)
* Line 1: d일간 수확할 수 있는 작물의 최대 갯수
2 3 60 7 1 2 40 3 2 30 1 3 50 2 2 10 1 1 20 2 1 10 1 1 30
6