Maximizing Album Score

Nikola loves collecting photos of football players and storing them in his album. He plans to collect photos from \(N\) teams, and each team has an album that can hold up to \(M\) photos. For each team, collecting \(x\) photos yields a score of \(B_x\) (with \(0 \le x \le M\)). Currently, for the \(i\)-th team, Nikola already has \(P_i\) photos in his album.

Nikola's friend Ivan is gifting him \(K\) extra photos. Nikola can distribute these \(K\) photos among the teams however he wishes, but the total number of photos for any team cannot exceed \(M\). Determine the maximum total score Nikola can achieve after optimally distributing the extra photos.

In other words, the problem can be described mathematically as follows. For each team \(i\), if Nikola adds \(t_i\) photos (where \(0 \le t_i \le M - P_i\)), then the score for the team is \(B_{P_i+t_i}\). The task is to maximize the sum \(\sum_{i=1}^{N} B_{P_i+t_i}\) under the constraint \(\sum_{i=1}^{N} t_i \le K\).

Note: The score values \(B_0, B_1, \dots, B_M\) are provided in input, and you can assume that \(B_x\) is non-decreasing with respect to \(x\).

inputFormat

The input consists of three lines:

• The first line contains three integers \(N\), \(M\), and \(K\) representing the number of teams, the maximum number of photos per team, and the number of extra photos gifted, respectively.
• The second line contains \(N\) space-separated integers \(P_1, P_2, \dots, P_N\), where \(P_i\) is the number of photos Nikola already has for the \(i\)-th team.
• The third line contains \(M+1\) space-separated integers \(B_0, B_1, \dots, B_M\), where \(B_x\) is the score obtained for having \(x\) photos of a team.

outputFormat

Output a single integer: the maximum total score Nikola can achieve after optimally distributing the extra \(K\) photos among the teams.

sample

1 5 2
3
0 1 2 4 7 11

11