めんどくさがり屋の買い出し

問題文

林くんは自炊を始めました。料理は楽しく気分転換になるので、かなり好意的に受け止めていますが、買い出しは別です。

かなり面倒なので、効率的に取り組みたいと思っています。

まず、冷蔵庫の大きさを$W$, $H$で書き出します。

そこで、いつもお母さんが調理に用いていた要冷蔵の食材$N$種類を「大きさ」($w_i$, $h_i$)と「消費期限日数残高」($d_i$)の項目に則って書き出してみました。

---

$T$回の自炊の予定があります。

「消費期限を切らせない」ことと「冷蔵庫に入る量しか買わない」ことを絶対条件とします。

意識低い系の林くんは、必要であれば、配置の際の食材の回転もいといません。

買い出しは、必要であれば、毎料理前に行うことにしています。

---

林くんは生ものは食べられません。

各食材の依存関係を表すグラフが$M$個の辺($u_i$, $v_i$)として与えられます。

毎料理は、任意の連結成分のうちのどれか一つを選び、その中のすべての食材を1つずつ消費します。

---

消費期限日数残高は、料理を経るたびに$1$減ります。$0$以下になった時点で、終了です。

(林くんは罪悪感でのたうち回ります)

---

冷蔵庫は初めは空です。

林くんが最低何回の買い出しに行く必要があるかを求めてください。

もし、1回でも料理を行えないようであれば、$-1$を出力してください。

制約

• $1 \leq W, H \leq 1000$
• $1 \leq N \leq 8$
• $1 \leq w_i, h_i \leq \min(W, H)$
• $1 \leq d_i \leq 300$
• $1 \leq T \leq 300$
• $0 \leq M \leq N-1$
• $1 \leq u_i \lt v_i \leq N$

※テストケースは未作成です。