March Break Contest '22 Problem 3 - Terradog's Gifts

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type

Terradog is purchasing gifts for his friend Stacy! In front of him are N stores which he can choose to purchase gifts from. Each store sells exactly 1 type of item, and he can purchase a maximum of 1 item per store. He can purchase from as many stores as he wants. Terradog knows that the item at the i-th store has a quality of q_i. He also knows that the value of the item at the i-th store is v_i.

In order for the gift to be as perfect as possible, Terradog wants all items he purchases to be of quality X. Luckily, he has a special move he can use up to K times! Terradog has an array of M integers, each with value a_i. On any move, he can increase the quality of an item purchased at the i-th store by any a_i from his array.

Terradog would like to give Stacy a gift with the maximum possible total value, whilst also ensuring all purchased items are of quality X. Can you output what the maximum possible total value of gifts he can obtain is?

Input Specifications

The first line will contain four space-separated integers, N (1 \leq N \leq 10^5), M (1 \leq M \leq 10^3), K (1 \leq K \leq 10^3), and X (1 \leq X \leq 10^5), the number of stores Terradog can purchase from, the length of Terradog's array, the number of times Terradog can use his move, and the quality Terradog wants to make all his gifts, respectively.

The next line will contain N space-separated integers, q_1, q_2, \ldots, q_N (1 \leq q_i \leq 10^5), where q_i represents the quality of the item purchased at the i-th store.

The next line will contain N space separated integers, v_1, v_2, \ldots, v_N (1 \leq v_i \leq 10^5), where v_i represents the value of the item purchased at the i-th store.

The next line will contain M space-separated integers, a_1, a_2, \ldots, a_M (1 \leq a_i \leq 10^5), where a_i is a value in Terradog's array.

Output Specifications

Output a single integer, the maximum possible total value of gifts Terradog can obtain.


Subtask 1 [10%]

N, M, K, X \leq 10

Subtask 2 [90%]

No additional constraints.

Sample Input

4 3 4 14
1 14 4 2
80 1 2 4
1 4 6

Sample Output



Terradog can first purchase a gift from shop 2, with a quality of 14 and a value of 1. He can then use his move 3 times on shop 1, increasing the quality by 6, 6, and 1, for a total quality of 14. He can then purchase the gift with a value of 80. In total, the combined value will be 1 + 80 = 81.


There are no comments at the moment.