주문 선택과 기계 대여

목수 샘은 $N$개의 주문을 받았습니다. 이 주문들을 완성하려면 아직 가지고 있지 않은 $M$대의 기계가 필요합니다. 모든 주문이 모든 기계를 요구하지는 않지만, 각 주문은 적어도 한 대의 기계를 필요로 합니다.

한 주문을 완성하려면, 샘은 그 주문이 요구하는 각 기계에 대해 그 기계를 구매하거나 대여해야 합니다. 기계마다 필요한 작업량이 주문에 따라 다르기 때문에, 기계의 대여료는 그 기계를 사용하는 주문에 따라 달라집니다. 반면 기계의 구매 가격은 어떤 주문과도 무관하며, 한 번 구매한 기계는 추가 비용 없이 원하는 만큼 여러 주문에 사용할 수 있습니다.

어떤 주문의 비용이 그 수익보다 크다면, 샘은 그 주문을 거절할 수 있습니다. 거절한 주문은 수익도 비용도 발생시키지 않습니다.

주문 $i$의 수익은 $v_i$입니다. 이 주문을 완성하려면 정해진 기계 집합이 필요하며, 필요한 각 기계 $j$의 대여료는 $r_{ij}$입니다. 기계 $j$의 구매 가격은 $s_j$입니다.

샘의 이익(완성한 주문들의 총 수익에서 모든 구매 및 대여 비용을 뺀 값)이 최대가 되도록, 어떤 주문을 완성하고, 어떤 기계를 구매하고, 어떤 기계를 대여할지 결정하세요. 모든 주문을 거절하면 이익이 $0$이 되므로, 정답은 결코 음수가 되지 않습니다.

첫째 줄에 두 정수 $N$과 $M$이 주어집니다 ($1 \le N \le 1200$, $1 \le M \le 1200$).

이어서 $N$개의 주문 블록이 주어집니다. 주문 $i$의 블록은 두 정수, 즉 수익 $v_i$ ($1 \le v_i \le 5000$)와 필요한 기계의 수 $m_i$ ($1 \le m_i \le M$)가 적힌 줄로 시작합니다. 이어지는 $m_i$개의 줄에는 각각 두 정수 $j$와 $r_{ij}$ ($1 \le j \le M$, $1 \le r_{ij} \le 20000$)가 주어지며, 이는 주문 $i$가 필요로 하는 기계와 이 주문에 그 기계를 사용할 때의 대여료를 뜻합니다.

마지막 주문 블록 뒤에는 $M$개의 줄이 오고, $j$번째 줄에는 정수 $s_j$ ($1 \le s_j \le 20000$), 즉 기계 $j$의 구매 가격이 하나 주어집니다.

달성할 수 있는 최대 이익을 정수 하나로 출력합니다.

첫 번째 예제에서 최대 이익 $50$은 두 가지 방법으로 얻을 수 있습니다.

• 주문 $2$를 거절하고 주문 $1$을 완성하며 기계 $1$과 기계 $2$를 모두 대여합니다.
• 두 주문을 모두 완성하고 기계 $1$을 구매하며 기계 $2$와 기계 $3$을 대여합니다.

어느 방법을 택하든 이익은 $50$입니다.