Bộ chứng minh tham lam (Greedy Proof Set)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Bài gồm bốn tình huống độc lập để luyện nhận dạng lựa chọn tham lam. (A) Chọn đúng $K$ giá nhỏ nhất trong một dãy và in tổng. (B) Chọn ít phần tử nhất trong các dung lượng để tổng đạt ít nhất $T$. (C) Đổi số tiền $V$ bằng các tờ $1,5,10,20,100$ với số tờ ít nhất. (D) Từ một chuỗi nhị phân không có số $0$ đầu, xóa đúng một bit để giá trị còn lại lớn nhất. Hãy in đáp án của bốn phần theo thứ tự.

Input

Phần A: một dòng $n_A,K$, rồi một dòng $n_A$ giá. Phần B: một dòng $n_B,T$, rồi một dòng $n_B$ dung lượng, bảo đảm tổng đủ $T$. Phần C: một dòng chứa $V$. Phần D: một dòng chứa chuỗi nhị phân $s$.

Output

In bốn dòng: tổng nhỏ nhất của A; số phần tử ít nhất của B; số tờ ít nhất của C; chuỗi lớn nhất của D.

Subtask

Các giới hạn chung:

• $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 điểm): $n_A,n_B \le 20$, $|s| \le 20$

• Subtask 2 (30 điểm): $n_A,n_B \le 200$, $|s| \le 5000$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

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

Output

7
2
5
11010

Giải thích

A: $1+2+4=7$. B: hai dung lượng lớn nhất $6+4=10$, nên cần $2$. C: $43=20+20+1+1+1$, cần $5$ tờ. D: xóa chữ số 0 đầu tiên để được 11010.