След като влезе в университета много неща в живота на Ели се промениха. Едно от тях е пътят ѝ до учебното заведение.

Нека представим града, в който живее момичето, като правоъгълна матрица с N реда и M колони, в чиито клетки ще бъдат разположени домът ѝ, университетът, бензиностанции, или други обекти, които в случая няма да ни интересуват. За простота ще разглеждаме само подрегиона, в който има важни неща - така домът ѝ ще бъде с координати (1, 1), а университетът – с (N, M). Обектите, които ни интересуват, са единствено K-те бензиностанции, разположени в (R₁, C₁), (R₂, C₂), ..., (R_K, C_K). Всяка от тях си има собствена тарифа P_i за зареждане, която е възможно дори да бъде отрицателна, ако се случи така, че да е собственост на чичо ѝ, например. Денивелацията на терена разрешава от бензиностанция i да се пропътуват максимум V_i единици по вертикала и H_i по хоризонтала. Ели е доста праволинейна, за това пътува единствено надолу и надясно.

Можете ли да определите каква е минималната цена, за която Елеонора може да стигне от дома си до университета, спазвайки наложените ограничения? На първия ред на стандартния вход ще бъдат зададени три естествени числата N, M и K – съответно броят редове, колони и бензиностанции. На всеки от следващите К реда ще има по пет естествени числа – R_i, C_i, P_i, V_i, H_i – съответно редът и колоната, на които се намира бензиностанцията, цената за зареждане, и максималните разстояния по вертикала и хоризонтала, които може да се изминат от там. Гарантирано е, че няма две бензиностанции в една точка, и също така няма да има бензиностанция в точката на университета. На единствен ред на стандартния изход изведете едно цяло число – минималната сума, с която Ели може да се придвижи от дома си до университета, или Impossible ако това е невъзможно.

• 1 ≤ K ≤ 500,000
• 1 ≤ R_i + V_i ≤ N ≤ 1,000
• 1 ≤ C_i + H_i ≤ M ≤ 1,000
• -1000 ≤ P_i ≤ 1,000

Примерен Вход	Примерен Изход
5 6 4 1 1 7 3 3 2 2 13 1 4 3 3 35 2 3 3 5 27 2 1	42
4 4 1 1 2 -42 3 2	Impossible