Background

gcd has many pieces of clothing, and each piece has a different color.

Problem Description

gcd has a total of $n$ pieces of clothing, numbered $A_1, A_2, \cdots A_n$.

Each piece of clothing has a color value and a washing time. After wearing a piece of clothing, he will send it to be washed. The comfort value of that day depends on the product of the day's weather value and the clothing's color value, and the weather value can be negative.

Given the weather for $m$ days, find the maximum total comfort value.

If it is certain that there exists a day when gcd has no clothes to wear, output "gcd loves her clothes!" (without quotes).

Input Format

The input consists of $4$ lines.

Line $1$ contains $n, m$.

Line $2$ contains $x_1, x_2 \cdots x_n$, representing the color values of the clothes.

Line $3$ contains $y_1, y_2 \cdots y_n$, representing the washing times of the clothes.

Line $4$ contains $z_1, z_2 \cdots z_m$, representing the weather value of each day.

Output Format

Output $1$ line: the maximum total comfort value over $m$ days of wearing clothes, or output "gcd loves her clothes!".

2 5
5 10
1 1
2 4 3 5 2

125

Hint

Sample Explanation $1$

$A_1:Day_1,Day_3,Day_5$

$A_2:Day_2,Day_4$

Subtasks

For $30\%$ of the testdata, $n = 2$, $m = 100$.

For $50\%$ of the testdata, $n \leq 3$, $m \leq 1000$.

For $100\%$ of the testdata, $n \leq 4$, $n \neq 1$, $m \leq 2000$, $y_i \leq 6$, $Maxy < m$, $|z_i| \leq 10^8$.

Source

MtOI2018 迷途の家の水题大赛 T3

Problem setter: b2019dy

78488

Translated by ChatGPT 5