Dán Giấy Tường

Boris muốn dán giấy tường cho căn hộ mới mua. Căn hộ có $n$ phòng, mỗi phòng có dạng hình hộp chữ nhật với chiều dài, chiều rộng và chiều cao đã biết.

Có $m$ loại giấy tường để chọn. Mỗi cuộn giấy tường có chiều dài, chiều rộng và giá bán xác định. Giấy có các sọc dọc theo chiều dài cuộn nên khi dán bắt buộc phải đặt sọc thẳng đứng (không được xoay ngang cuộn giấy, kể cả khi chiều dài nhỏ hơn chiều rộng). Một cuộn có thể được cắt thành nhiều miếng, nhưng các đường ghép cũng phải thẳng đứng.

Mỗi phòng chỉ được dán bằng một loại giấy duy nhất, và các miếng cắt từ cùng một cuộn không được dùng chung cho hai phòng khác nhau, nghĩa là mỗi phòng phải mua các cuộn riêng. Cho phép sử dụng không hết một cuộn.

Hãy tính chi phí tối thiểu để dán giấy tường cho toàn bộ căn hộ.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$: số phòng.
• $n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương: chiều dài, chiều rộng và chiều cao của một phòng (mét).
• Dòng tiếp theo chứa số nguyên dương $m$: số loại giấy tường.
• $m$ dòng cuối, mỗi dòng chứa ba số nguyên dương: chiều dài cuộn, chiều rộng cuộn và giá một cuộn.

Dữ liệu ra

Một số nguyên duy nhất: tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n,m\le 500$
• Mọi số trong dữ liệu vào đều dương và không vượt quá $500$.
• Dữ liệu đảm bảo luôn tồn tại cách dán cho mọi phòng.

Ví dụ