A histogram is a polygon composed of a sequence of rectangular bars aligned at a common base line. All bars have equal widths but may have different integer heights. Additionally, each bar is fully colored with a single color. For example, the figure below shows the histogram that consists of bars with the heights 2, 3, 1, 7, 1, 3, 5, measured in units where 1 is the width of each bar. In this case, every bar is colored with one out of three colors. There are a lot of rectangles that can be placed inside this histogram (infinitely many, in fact). We will say that a rectangle is nice if and only if: • It lies completely inside the histogram. • It covers one or several regions of positive area for every color in the histogram (barely touching an area is not enough; the total area covered for each color must be strictly positive). Here are some examples of rectangles that are not nice: The rectangles in the two leftmost figures are not nice because they don’t lie completely inside the histogram. The rectangle in the rightmost figure is not nice because the total white area covered is not strictly positive, and a nice rectangle must cover a positive area of every color. On the other hand, here are some examples of nice rectangles:
2/3 The area of the nice rectangle in the leftmost figure is 6 × 1 = 6 square units, the area of the nice rectangle in the middle figure is 3×3 = 9 square units and the area of the nice rectangle in the rightmost figure is 1.8 × 2.6 = 4.68 square units. Clearly, the area of the rectangle in the middle figure is largest. In fact, it turns out it doesn’t exist a nice rectangle for this histogram with a larger area! In this problem, you are given a histogram and your task is to compute the maximum area of all the possible nice rectangles. By the way, it is not hard to prove that this area will always be an integer. Input The input contains several test cases (at most 50). Each test case is described by several lines. The first line contains two integer N and C, the number of bars and the total number of colors in the histogram, respectively (1 ≤ N ≤ 105 and 1 ≤ C ≤ min(30,N)). The following line contains N integers hi, the height of the i-th bar from left to right (1 ≤ hi ≤ 109). The following line contains N integers ci, the color of the i-th bar from left to right. Each color is represented as an integer between 0 and C − 1, inclusive. You can assume that for each histogram there will be at least one bar of every color. The last line of the input contains two zeros and should not be processed. Output For each test case, output a single integer on a single line — the area of the largest nice rectangle for this histogram. Explanation of the sample cases: Below are some of the sample test cases with their respective largest nice rectangles: Example 2 Example 3 Example 4 Example 6 Sample Input 63 231735 Example 5
3/3 201012 31 222 000 52 32123 10101 64 123456 012310 72 1234321 0101010 10 2 2121121221 1000100110 32 1000000000 999999997 999999999 011 00 Sample Output 9 6 5 12 10 10 2999999991