Minimum Total Cost for Image Filters

You must process n images, each with its own filter cost and required processing interval. Applying the filter associated with image i costs filterCost[i]. Image i must be processed on a schedule covering every day from startDay[i] through endDay[i], inclusive.

A daily discounted option is also available: discountPrice allows a filter to be applied to all images at the discounted rate. Choose how to process the images so that every required interval is covered at the lowest possible cost.

Return the minimum total cost modulo 10^9 + 7.

Input

• n: the number of images.
• filterCost: the cost associated with each image's filter.
• startDay: the first processing day for each image.
• endDay: the final processing day for each image.
• discountPrice: the discounted daily price.

Output

Return the minimum total cost needed to process all images.

Example

Input:

• n = 3
• filterCost = [2, 4, 3]
• startDay = [1, 2, 3]
• endDay = [2, 3, 4]
• discountPrice = [0]

Output: 6

Explanation: Choosing the discounted option on days 2 and 3 produces a total cost of 6.