h084.
4. 牆上海報
內容
有一個由 $n$ 個木板所組成的柵欄，每個木板的高度為 $h[1], h[2], ..., h[n]$，有 $k$ 張海報要張貼在柵欄上，每張海報的寬度為 $w[1], w[2], \cdots, w[n]$ 並且高度均為 $1$。
若要張貼海報在高度為 $x$ 的高度，則第 $i$ 張海報需要張貼在一個長度為 $w[i]$ 的連續並且高度都不小於 $x$ 的木板上，且每張海報張貼的高度需要一致、按照順序並不能重疊 (可以相連)。詢問最高可以貼到多高的位置。
輸入說明
第一行有兩個正整數 $n, k$，接下來一行有 $n$ 個正整數代表每個木板的高度，最後一行有 $k$ 個正整數代表每張海報的寬度。
數字範圍
- $1 \leq n \leq 200000$
- $1 \leq k \leq 5000$
- $1 \leq h_i \leq 10^9$
- $\sum w_i \leq n$
子題配分
- (20%): $1\leq n \leq 100, k=1$
- (40%): $k=1$
- (40%): 無額外限制
輸出說明
輸入最大可以張貼的高度。
範例輸入
#1
5 1 6 3 7 5 1 3
範例輸出
#1
3
範例輸入
#2
10 3 5 3 7 5 1 7 5 3 8 4 2 2 1
範例輸出
#2
5
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <10M
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <10M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1K
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <10M
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <10M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1K
提示 ：
範例 2
柵欄長相如下圖，三張海報 (寬度為 2, 2, 1) 可以貼在高度為 $5$ 的高度。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 36818 | fire5386 (becaidorz) | h084 | 299 | 2023-08-10 14:21 | |
| 34515 |
|
h084 | 280 | 2023-03-26 22:29 | |
| 34426 |
|
h084 | 476 | 2023-03-17 22:38 | |
| 33242 |
|
h084 | 555 | 2022-12-15 22:21 | |
| 28889 |
|
h084 | 1198 | 2022-01-10 12:28 |