Greedy Proof Set

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

The input contains four independent greedy exercises. (A) Choose exactly $K$ smallest prices and print their sum. (B) Choose the minimum number of capacities whose sum reaches at least $T$. (C) Represent amount $V$ using denominations $1,5,10,20,100$ with the fewest notes. (D) Delete exactly one bit from a binary string with no leading zero to maximize the remaining value. Print the four answers in order.

Input

Part A: one line $n_A,K$, then one line with $n_A$ prices. Part B: one line $n_B,T$, then one line with $n_B$ capacities, whose total is guaranteed to reach $T$. Part C: one line with $V$. Part D: one line with binary string $s$.

Output

Print four lines: the minimum sum for A; the minimum count for B; the minimum note count for C; and the maximum binary string for D.

Subtasks

General constraints:

• $1 \le K \le n_A \le 1000$.

• $1 \le p_i \le 10^6$.

• $1 \le n_B \le 1000$, $1 \le T \le 10^9$.

• $1 \le b_i \le 10^9$, $\sum b_i \ge T$.

• $1 \le V \le 10^9$.

• $2 \le |s| \le 10^5$.

• Subtask 1 (20 points): $n_A,n_B \le 20$, $|s| \le 20$

• Subtask 2 (30 points): $n_A,n_B \le 200$, $|s| \le 5000$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

5 3
8 2 5 1 4
4 10
6 4 3 2
43
110010

Output

7
2
5
11010

Explanation

A: $1+2+4=7$. B: the two largest capacities $6+4=10$, so the answer is $2$. C: $43=20+20+1+1+1$, requiring $5$ notes. D: deleting the first 0 gives 11010.