Storage Cost Rules

The storage cost is determined as follows:

1. For a batch of M files that contains X sensitive files, cost is M * X * encCost, where encCost is the encryption cost for sensitive files. This is applicable only when batch contains at least 1 sensitive file.
2. For a batch of M files with 0 sensitive files, the cost is a constant flatCost.
3. If the no of files in a batch M is divisible by 2 then:
   • store the entire batch in bucket and calculate cost using rule 1 or 2, or
   • split the batch into 2 equal parts and total cost will be the sum of the costs for smaller batches

Note: When splitting a batch into two files, both must remain in their original order.
For example, given a batch containing files 1, 4, 2, 6, the only split is into {1, 4} and {2, 6}. You cannot reshuffle the files into different groupings like {1, 2} and {4, 6}. Though B1 can further be split into {1} and {4}, and similarly B2 can be split into {2} and {6}. You are to compute the minimum storage cost while maintaining the rules constraints.

Function Description

Compute and return the minimum possible storage cost for the batch using the rules above.

Method Signature

long getMinimumStorageCost(int n, int encCost, int flatCost, int[] sensitiveFiles)

Parameters

• n: number of files in the batch (files are labeled from 1 to n)
• encCost: encryption cost multiplier
• flatCost: cost of storing a batch with 0 sensitive files
• sensitiveFiles: array containing the file numbers that are sensitive

Returns

• The minimum total storage cost as a long.

Examples

Example 1

Input

n = 4
encCost = 5
flatCost = 3
sensitiveFiles = []

Explanation

• Initial batch is {1, 2, 3, 4} with X = 0 sensitive files.
• Storing the full batch costs flatCost = 3 (rule 2).
• Since M = 4 is divisible by 2, you may split, but splitting into two batches with 0 sensitive files would cost 3 + 3 = 6, which is higher.
• Minimum cost is 3.

Output

3

Example 2

Input

n = 2
encCost = 2
flatCost = 1
sensitiveFiles = [1, 3]

Given

Batch = {1, 2, 3, 4}, where files 1 and 3 are sensitive.

Approach 1

• Store all on single bucket
• Batch size is 4 with 2 sensitive files, using rule 1 gives cost: 4 * 2 * 2 = 16

Approach 2

• Split into two equal parts: {1, 2} and {3, 4}
• For {1, 2}: M = 2, X = 1
  • Store whole: 2 * 1 * 2 = 4
  • Or split into {1} and {2}: {1} costs 1 * 1 * 2 = 2, {2} costs flatCost = 1, total 2 + 1 = 3
  • Minimum for {1, 2} is 3
• For {3, 4}: similarly minimum cost is 3
• Total cost after split: 3 + 3 = 6

Output

6

Example 3

Input

n = 2
encCost = 3
flatCost = 10
sensitiveFiles = [1, 2, 3, 4]

Explanation

• Initial batch {1, 2, 3, 4} has M = 4, X = 4.
• Store whole cost: 4 * 4 * 3 = 48.
• If you split into {1, 2} and {3, 4}: each has M = 2, X = 2, store whole cost 2 * 2 * 3 = 12, total 12 + 12 = 24.
• Further splitting into singletons would cost 4M = 1, X = 1: cost 1 * 1 * 3 = 3 each, total 12, which is the minimum here.

Output

12