欸批奚欸斯奚礦帶是一條長度為 $N$ 公尺的直線礦帶,富商竹竹為了開採秘銀礦,便把礦帶分成了 $N$ 個長度為 $1$ 公尺的礦區並依序編號為 $1$ 到 $N$ ,並記錄含有秘銀礦的礦區編號,然而,礙於技術限制,竹竹只能使用三種規格的採礦機,三種採礦機分別可以開採 $1$ 、 $7$ 、 $30$ 個連續礦區,架設三種採礦機的成本分別為 $b_1, b_2, b_3$。順帶一提,因為竹竹很有錢,所以也連帶買下了礦帶周圍的土地,也就是說採礦機的開採範圍就算超出礦帶也是沒有問題的。
於是,竹竹來向聰明的你請求協助,他希望你可以幫他計算開採所有的秘銀礦礦區所需要花費的最低成本。
輸入一共有三行。
第一行包含兩個以空白分隔的正整數 $N, M\ (1 \le M \le N \le 10^ 5)$ 代表礦帶的長度以及含有秘銀礦的礦區數量。
第二行包含 $M$ 個以空白分隔的正整數 $a_i\ (1 \le a_i \le N, a_i > a_j \forall i > j)$ 代表第 $i$ 個含有秘銀礦的礦區編號。
第三行包含三個以空白分隔的正整數 $b_1, b_2, b_3\ (1 \le b_1, b_2, b_3 \le 10^ 7)$ 代表架設三種採礦機的成本。
請輸出一個整數,代表開採所有含秘銀礦的礦區所需要的最低成本。
LeetCode 983
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~26 | 無額外限制 | 100 |