A bakery needs to bake a batch of loaves of various recipes. There are K different recipe types, indexed from 1 to K. For each recipe i, the bakery must bake cnt[i] loaves. Each loaf takes exactly one oven slot and the oven slots are processed sequentially (slot 1, slot 2, slot 3, and so on).

The recipes are partitioned into G independent groups, numbered from 1 to G. The group of recipe i is given by grp[i]. Recipes in the same group share physical tins, which introduces a cooldown constraint:

• Normally, any two consecutive loaves of the same group must be separated by at least n slots. That is, if a loaf of group g is baked at slot x, the next loaf of group g can be baked at slot y, where y - x >= n + 1.
• The bakery has one blast chiller. For each group, the blast chiller can be used at most once. This allows the bakery to reduce the required separation between one specific pair of consecutive loaves such that the gap is at least ceil(n / 2) slots. That is, for this pair, y - x >= ceil(n / 2) + 1. The choice of whether and where to use the blast chiller is independent for each group.

Slots can be used to bake loaves of different groups, or they can be left idle.

Find the minimum total number of slots (i.e., the index of the last active slot, assuming we start at slot 1) required to bake all loaves of all recipes.

Input Format

• The first line contains an integer, K, denoting the number of recipe types.
• The second line contains an integer, n, denoting the minimum cooldown slots required between consecutive loaves of the same group.
• The third line contains an integer, G, denoting the number of independent groups.