Potatoes

Problem

Gaccho owns an N-sided field and M potatoes. Each field is numbered from 1 to N. Gaccho wants to increase the number of potatoes by planting and harvesting potatoes in the field.

Gaccho lives alone and can only manage fields up to the K side. In addition, the soil condition and area of ​​each field vary, and the number of potatoes harvested and the number of potatoes that can be planted also vary. When potatoes are planted in field i, ai potatoes can be harvested for each potato planted in field i one year later. However, only bi potatoes can be planted in the field i at the maximum.

When you plant M or less potatoes in a field within K side, please find the maximum number of potatoes you can own one year later.

Constraints

• 1 ≤ N ≤ 15
• 1 ≤ M ≤ 104
• 1 ≤ K ≤ min (N, 3)
• 1 ≤ ai ≤ 103
• 1 ≤ bi ≤ 104

Input

The input is given in the following format.

NMK a1 a2 ... aN b1 b2 ... bN

Three integers N, M, K are given on the first line, separated by blanks. N integers ai are given on the second line, separated by blanks. N integers bi are given on the third line, separated by blanks.

Output

Output the maximum number of potatoes in one line.

Examples

Input

5 100 3 2 3 4 5 6 50 40 20 10 5

Output

280

Input

5 100 3 2 3 4 5 100 50 40 20 10 1

Output

339

inputFormat

Input

The input is given in the following format.

NMK a1 a2 ... aN b1 b2 ... bN

Three integers N, M, K are given on the first line, separated by blanks. N integers ai are given on the second line, separated by blanks. N integers bi are given on the third line, separated by blanks.

outputFormat

Output

Output the maximum number of potatoes in one line.

Examples

Input

5 100 3 2 3 4 5 6 50 40 20 10 5

Output

280

Input

5 100 3 2 3 4 5 100 50 40 20 10 1

Output

339

样例

5 100 3
2 3 4 5 6
50 40 20 10 5

280