纜車上的陪同者

題目敘述

山上的纜車站有 n 位遊客，第 i 位遊客的體重為 w_i，類別為 t_i：t_i=1 表示兒童，t_i=0 表示大人。站方有 K 台纜車，每位遊客必須恰好搭乘其中一台，每台最多載 2 人，空車也可以。

• 兒童不能單獨搭車，也不能和另一位兒童同車，必須和一位大人同車。
• 大人可以單獨搭一台、和另一位大人同車，或陪同一位兒童。

一台纜車的載重是車上乘客的體重總和。站方要設定一個整數載重上限 W，每台車的載重都不能超過 W（剛好等於 W 可以）。請求出能讓所有遊客搭完的最小 W。若不論 W 多大都無法安排，輸出 -1。

輸入格式

第一行有兩個整數 n、K。 第二行有 n 個整數 w₁,…,w_n。 第三行有 n 個整數 t₁,…,t_n。

輸出格式

輸出一個整數，為最小的 W，或 -1。

限制

• 1 ≤ n ≤ 2 × 10⁵
• 1 ≤ K ≤ n
• 1 ≤ w_i ≤ 10⁹
• t_i ∈ {0,1}
• 時間限制 1 秒

子題配分

1. （20 分）n ≤ 14。
2. （30 分）所有 t_i=0。
3. （50 分）無額外限制。

範例

範例 1

輸入

5 3
30 50 20 60 40
1 0 0 0 0

輸出

70

範例 2

輸入

4 2
5 5 5 5
1 0 0 0

輸出

10

說明

範例 1：兒童體重 30，大人體重 20、40、50、60，共 3 台車。若兒童搭配最輕的大人 20，剩下 40、50、60 只能用 2 台車，必有一對同車，最小載重和是 40+50=90。改讓兒童搭配 40（載重 70），再讓 20 和 50 同車（載重 70），60 單獨一台，三台車最大載重為 70。W=69 以下無法安排，答案為 70。

範例 2：兒童搭一位大人載重 10，另外兩位大人同車載重 10，剛好等於 W 也算合法。

範例

範例 1

5 3
30 50 20 60 40
1 0 0 0 0

70

兒童 30 配大人 40（載重 70），20 與 50 同車（70），60 單獨一台，最大載重 70。若兒童配最輕的 20，剩下三位大人至少要有一對同車，載重和至少 90。

範例 2

4 2
5 5 5 5
1 0 0 0

10

兒童配一位大人載重 10，另外兩位大人同車載重 10。剛好等於 W 算合法，所以答案是 10。