GCD's Maximized Comfort

GCD owns n clothes, labeled \(A_1, A_2, \cdots, A_n\). Each piece of clothing has a color value \(c_i\) and a washing time \(t_i\). Every day, after wearing a cloth, GCD sends it for washing. A cloth worn on day \(d\) yields a comfort value equal to the product of that day’s weather \(w_d\) and its color value \(c_i\) (note that \(w_d\) may be negative).

GCD has the weather forecast for \(m\) days. On each day he must choose exactly one available cloth to wear. If he wears cloth \(i\) on day \(d\), it will not be available until day \(d+t_i\); the other clothes remain available if they are not in washing. If at some day there is no available cloth, the schedule is considered impossible.

Your task is to choose a cloth for each day (possibly reusing clothes when they become available) so as to maximize the total comfort value over the \(m\) days. If it is inevitable that on some day GCD does not have any available cloth, output gcd loves her clothes!.

inputFormat

The input begins with two integers \(n\) and \(m\) (the number of clothes and the number of days).

Then follow \(n\) lines, each containing two integers \(c_i\) and \(t_i\) (the color value and washing time of the \(i\)th cloth).

The last line contains \(m\) integers, representing the weather value \(w_1, w_2, \dots, w_m\) for each day.

It is guaranteed that all numbers are integers.

outputFormat

If it is possible to schedule a cloth for each day, output the maximum total comfort value achievable. Otherwise, output gcd loves her clothes! (without quotes).

sample

2 3
5 2
3 1
2 -1 3

22