輸入首行有兩個整數 $N, M$，代表變數的個數以及規則的個數。

接下來一行 $M$ 個數字 $w_1, w_2, \ldots, w_M$，代表當第 $i$ 條規則被滿足時，8e7 必須付出 $w_i$ 的代價。

緊接著 $M$ 行，第 $i$ 行代表第 $i$ 條規則的滿足條件，其形式會如題敘內寫的呈現。

• $1 \leq N, M \leq 500$
• $1 \leq w_i \leq 10^ 6$
• $1 \leq a, b, c, d \leq N$
• $0 \leq p, r < 10^ 5$
• $0 < q, s \leq 10^ 5$

首行輸出一行一個整數，代表 8e7 在最佳的變數賦值情況下，他需要付出的最小代價總和。

接下來一行 $N$ 個整數 $v_1, v_2, \ldots, v_N$ 以單一空格間隔隔開，代表你提供的一種最佳的變數賦值方法，滿足變數 $i$ 的值為 $v_i$。

在最小代價總和輸出正確後，你的答案會被視為正確若且唯若當你提供的變數賦值滿足：

• $0 \leq v_i \leq 10^ 5$
• 該變數賦值滿足的規則代價總和為最小代價總和

而若有多種賦值方法，輸出任何一種皆會視為正確。

• 當你的最小代價總和輸出正確，但輸出的賦值方法不正確時，你依然可以獲得一半的分數。但請注意，你一定要輸出隨意一種賦值方法，也就是說，只輸出一行最小代價總和是不會獲得分數的，你必須至少例如直接在第二行輸出 $N$ 個 $0$ 才可以通過 checker 的檢查。