클라우드 컴퓨팅

Johnny는 클라우드로 컴퓨팅 자원을 제공하는 회사 Bytecomp을 세우려 한다. 이런 회사는 보통 고객의 연산을 처리할 빠른 컴퓨터를 여러 대 갖춘다.

Johnny는 아직 컴퓨터를 한 대도 사지 않았다. 그는 컴퓨터 가게에 가서 판매 중인 컴퓨터 n대의 목록을 받았다. 각 컴퓨터는 코어 수 $c_i$, 클럭 속도 $f_i$, 가격 $v_i$로 나타낸다. 이런 컴퓨터에는 서로 간섭하지 않는 코어가 $c_i$개 있으므로 각 코어를 서로 다른 작업에 배정할 수 있다.

고객이 자원을 주문하면 필요한 코어 수 $C_j$와 최소 클럭 속도 $F_j$를 말한다. 주문에는 고객이 지불할 금액 $V_j$도 함께 있다. 주문을 받으면 Bytecomp은 고객이 요구한 연산 능력을 배타적으로 제공해야 한다. Johnny는 클럭 속도가 $F_j$ 이상인 코어 $C_j$개를 골라야 하며, 서로 다른 컴퓨터에서 골라도 된다. 그 코어들은 다른 주문에 배정할 수 없다.

Johnny가 최대한 많이 벌도록 도와주자. 받을 주문의 부분집합과, 받은 주문을 모두 처리할 컴퓨터의 부분집합을 고르면 된다. 목표는 고객에게 연산 능력을 제공해서 얻는 수익에서 컴퓨터를 사는 데 든 비용을 뺀 총이익을 최대로 만드는 것이다.

표준 입력의 첫 줄에는 가게에서 판매하는 컴퓨터의 수 $n$ (1 ≤ n ≤ 2000)이 주어진다. 다음 $n$개 줄에는 컴퓨터 하나의 정보가 주어진다. 공백으로 구분된 세 정수 $c_i$, $f_i$, $v_i$ (1 ≤ c_i ≤ 50, 1 ≤ f_i ≤ 10^9, 1 ≤ v_i ≤ 10^9)가 주어지며 각각 코어 수, 클럭 속도, 가격을 나타낸다.

그다음 줄에는 주문의 수 $m$ (1 ≤ m ≤ 2000)이 주어진다. 다음 $m$개 줄에는 주문 하나의 정보가 주어진다. 공백으로 구분된 세 정수 $C_j$, $F_j$, $V_j$ (1 ≤ C_j ≤ 50, 1 ≤ F_j ≤ 10^9, 1 ≤ V_j ≤ 10^9)가 주어지며 각각 필요한 코어 수, 최소 클럭 속도, 고객이 지불할 금액을 나타낸다.

표준 출력의 한 줄에 얻을 수 있는 최대 총이익을 정수 하나로 출력한다.