Cho \(n\) xâu \(s_1,s_2,\ldots,s_n\). Chi phí để sử dụng xâu \(s_i\) là \(c_i\).
Lưu ý: Có thể sử dụng xâu \(s_i\) nhiều lần và chi phí là \(c_i\) nhân với số lần dùng.

Yêu cầu: Tìm chi phí tối thiểu để sử dụng các xâu \(s_i\) ghép lại với nhau thành xâu đối xứng.

Input

• Dòng đầu chứa duy nhất một số nguyên dương \(n\) (\(1\leq n \leq 50\)) là số lượng xâu.
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa xâu \(s_i\) và số nguyên \(c_i\) là xâu thứ i và chi phí để sử dụng (1 \(\leq |s_i| \leq 20; 1\leq c_i \leq 10^9\)).

Output

• In ra chi phí tối thiểu, in \(-1\) nếu không tạo được xâu đối xứng.

Example

3
ba 3
abc 4
cbaa 5

7

2
abcab 5
cba 3

11

2
abc 1
ab 2

-1