Language: C++

//Original Code:
//#include <self/utility>
//#include <self/debug>
//#include <self/string>
//using namespace std;
//
//map <string,int> dp[2];
//string a[55];
//string ra[55];
//int cost[55];
//int n;
//
//pair<int,pair<int,string> > check(string a,string b,int rev,bool debug=false)
//{
//	int nrev=!rev;
//	if(a.size()>b.size()) swap(a,b),nrev=!nrev;
//	string tb=b;
////	if(debug) cout<<tb.substr(a.size())<<endl;
//	b=b.substr(0,a.size());
//	if(a!=b) return mp(false,mp(0,""));
//	else return mp(true,mp(nrev,tb.substr(a.size())));
//}
//
//int main()
//{
////	freopen("input.txt","r",stdin);
//	cin>>n;
//	for(int i=0;i<n;i++)
//	{
//		cin>>a[i]>>cost[i];
//		ra[i]=a[i];
//		reverse(all(ra[i]));
//	}
//	set <pair<ll,pair<int,string> > > squ;
//	for(int i=0;i<n;i++)
//	{
//		if(dp[0].find(a[i])==dp[0].end() || dp[0][a[i]]>cost[i]) dp[0][a[i]]=cost[i];
//		squ.insert(mp(cost[i],mp(0,a[i])));
//	}
//	while(squ.size())
//	{
//		ll cost=squ.begin()->first;
//		string now=squ.begin()->second.second;
//		int rev=squ.begin()->second.first;
//		squ.erase(squ.begin());
//		if(dp[rev][now]!=cost) continue;
//		if(isPalindrome(now)) over(cost);
//		for(int i=0;i<n;i++)
//		{
////			bool debug=(rev==0 && now=="abc" && i==0);
//			pair<int,pair<int,string> > o=check(now,(rev?a[i]:ra[i]),rev);
//			if(o.first==false) continue;
//			if(!(dp[o.second.first].find(o.second.second)==dp[o.second.first].end()) && dp[o.second.first][o.second.second]<=cost+::cost[i]) continue;
//			dp[o.second.first][o.second.second]=cost+::cost[i];
//			squ.insert(mp(dp[o.second.first][o.second.second],o.second));
//		}
//	}
//	cout<<-1<<endl;
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define quickcin ios_base::sync_with_stdio(false);
const int mod=200003;
const int gmod=2;
const int inf=1039074182;
const ll llinf=1LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
#endif

#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream & operator << (ostream& cout,vector<T> vec)
{
	cout<<"{";
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i];
		if(i!=(int)vec.size()-1) cout<<',';
	}
	cout<<"}";
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream & cout,pair<T1,T2> p)
{
	cout<<"("<<p.first<<','<<p.second<<")";
	return cout;
}

template <typename T>
ostream & operator << (ostream & cout,set <T> s)
{
	vector <T> t;
	for(auto x:s) t.push_back(x);
	cout<<t;
	return cout;
}

template <typename T>
ostream & operator << (ostream &cout,queue <T> q)
{
	vector <T> t;
	while(q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout<<t;
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream &cout,map <T1,T2> m)
{
	for(auto &x:m)
	{
		cout<<"Key: "<<x.first<<' '<<"Value: "<<x.second<<endl;
	}
	return cout;
}

template <typename T>
T operator * (vector <T> v1,vector <T> v2)
{
	assert(v1.size()==v2.size());
	int n=v1.size();
	T res=0;
	for(int i=0;i<n;i++)
	{
		res+=v1[i]*v2[i];
	}
	return res;
}

template <typename T1,typename T2>
pair<T1,T2> operator + (pair<T1,T2> x,pair<T1,T2> y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}

template <typename T1,typename T2>
pair<T1,T2> operator - (pair<T1,T2> x)
{
	return make_pair(-x.first,-x.second);
}

template <typename T>
vector<vector<T> > operator ~ (vector<vector <T> > vec)
{
	vector <vector<T> > v;
	int n=vec.size(),m=vec[0].size();
	v.resize(m);
	for(int i=0;i<m;i++)
	{
		v[i].resize(n);
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			v[i][j]=vec[j][i];
		}
	}
	return v;
}
#endif

void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	reverse(vec.begin(),vec.end());
	for(int i=vec.size();i<len;i++)
	{
		putchar('0');
	}
	for(int i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}
#endif
#ifndef _SELF_STRING
#define _SELF_STRING 1
#ifndef _SELF_RAND
#define _SELF_RAND 1
#if __cplusplus < 201103L
long long _Rand_Gen_Num() {return 1LL*rand()*RAND_MAX+rand();}
int rand(int l,int r) {long long x=_Rand_Gen_Num();return x%(r-l+1)+l;}
#else
#include <bits/stdc++.h>
#include <time.h>
#include <chrono>
using namespace std; 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
#endif
#endif
struct StringHash
{
	template <typename T>
	inline bool checkPrime(T x)
	{
		for(T i=2;i*i<=x;i++)
		{
			if(x%i==0) return false;
		}
		return true;
	}
	inline int nextPrime(int x)
	{
		for(int i=x;;i++)
		{
			if(checkPrime(i)) return i;
		}
	}
	int *hh;
	int n;
	int prime;
	int mod;
	int *e;
	inline void init(int _n,int _prime=-1,int _mod=-1)
	{
		n=_n;
		if(_prime==-1) prime=nextPrime(rand(1e8,3e8));else prime=_prime;
		if(_mod==-1) mod=nextPrime(rand(8e8,1e9));else mod=_mod;
		hh=new int[n+5];
		e=new int[n+5];
		e[0]=1;
		for(int i=1;i<n;i++)
		{
			e[i]=1LL*e[i-1]*prime%mod;
		}
	}
	inline void feedString(char c[])
	{
		n=strlen(c);
		hh[0]=c[0];
		for(int i=1;i<n;i++)
		{
			hh[i]=(1LL*hh[i-1]*prime+c[i])%mod;
		}
	}
	inline int getHash(int pos,int len)
	{
		assert(pos+len<=n);
		return ((pos+len-1>=0?hh[pos+len-1]:0)-1LL*(pos-1>=0?hh[pos-1]:0)*e[len]%mod+mod)%mod;
	}
	inline bool same(int x,int y,int len)
	{
		if(x+len>n) return false;
		if(y+len>n) return false;
		return (getHash(x,len)==getHash(y,len));
	}
};

template <int P>
struct HashValue
{
	int hashValue[P];
	bool operator == (HashValue x)
	{
		for(int i=0;i<P;i++)
		{
			if(hashValue[i]!=x.hashValue[i]) return false;
		}
		return true;
	}
};

template <int P>
struct MultipleStringHash
{
	StringHash h[P];
	int n;
	inline void init(int _n)
	{
		n=_n;
		for(int i=0;i<P;i++)
		{
			h[i].init(n);
		}
	}
	inline void feedString(char c[])
	{
		for(int i=0;i<P;i++)
		{
			h[i].feedString(c);
		}
	}
	inline HashValue <P> getHash(int x,int len)
	{
		HashValue <P> g;
		for(int i=0;i<P;i++)
		{
			g.hashValue[i]=h[i].getHash(x,len);
		}
		return g;
	}
	inline bool same(int x,int y,int len)
	{
		return (getHash(x,len)==getHash(y,len));
	}
};

template <int P>
struct PalindromeHash
{
	StringHash h[P];
	StringHash rh[P];
	int n;
	void init(int _n)
	{
		n=_n;
		for(int i=0;i<P;i++)
		{
			h[i].init(n);
		}
		for(int i=0;i<P;i++)
		{
			rh[i].init(n,h[i].prime,h[i].mod);
		}
	}
	void feedString(char c[])
	{
		n=strlen(c);
		for(int i=0;i<P;i++)
		{
			h[i].feedString(c);
		}
		reverse(c,c+n);
		for(int i=0;i<P;i++)
		{
			rh[i].feedString(c);
		}
		reverse(c,c+n);
	}
	bool checkOdd(int x,int len)
	{
		for(int i=0;i<P;i++)
		{
			if(h[i].getHash(x,len)!=rh[i].getHash(n-x-1,len)) return false;
		}
		return true;
	}
	inline int maxOdd(int x)
	{
		int l=1,r=min(x+1,n-x),mid,res=1;
		while(l<=r)
		{
			mid=l+r>>1;
			if(checkOdd(x,mid))
			{
				res=mid;
				l=mid+1;
			}
			else
			{
				r=mid-1;
			}
		}
		return res;
	}
};

string tostring(int x)
{
	string res="";
	while(x)
	{
		res.push_back(x%10+'0');
		x/=10;
	}
	reverse(res.begin(),res.end());
	return res;
}

int toint(string c)
{
	int res=0;
	for(auto &x:c)
	{
		res=res*10+x-'0';
	}
	return res;
}

vector <int> toint(vector <string> vec)
{
	vector <int> res;
	for(auto &x:vec)
	{
		res.push_back(toint(x));
	}
	return res;
}

inline vector <string> split(string x,char c)
{
	int l=x.size();
	vector <string> vec;
	int front=0;
	for(int i=0;i<l;i++)
	{
		if(x[i]==c)
		{
			if(i) vec.push_back(x.substr(front,i-front));
			front=i+1;
		}
	}
	if(x.back()!=c) vec.push_back(x.substr(front,(int)x.size()-front));
	return vec;
}

inline bool isPalindrome(string x)
{
	int len=x.size();
	for(int i=0;i<len/2;i++)
	{
		if(x[i]!=x[len-1-i]) return false;
	}
	return true;
}
#endif
using namespace std;

map <string,int> dp[2];
string a[55];
string ra[55];
int cost[55];
int n;

pair<int,pair<int,string> > check(string a,string b,int rev,bool debug=false)
{
	int nrev=!rev;
	if(a.size()>b.size()) swap(a,b),nrev=!nrev;
	string tb=b;
//	if(debug) cout<<tb.substr(a.size())<<endl;
	b=b.substr(0,a.size());
	if(a!=b) return mp(false,mp(0,""));
	else return mp(true,mp(nrev,tb.substr(a.size())));
}

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>cost[i];
		ra[i]=a[i];
		reverse(all(ra[i]));
	}
	set <pair<ll,pair<int,string> > > squ;
	for(int i=0;i<n;i++)
	{
		if(dp[0].find(a[i])==dp[0].end() || dp[0][a[i]]>cost[i]) dp[0][a[i]]=cost[i];
		squ.insert(mp(cost[i],mp(0,a[i])));
	}
	while(squ.size())
	{
		ll cost=squ.begin()->first;
		string now=squ.begin()->second.second;
		int rev=squ.begin()->second.first;
		squ.erase(squ.begin());
		if(dp[rev][now]!=cost) continue;
		if(isPalindrome(now)) over(cost);
		for(int i=0;i<n;i++)
		{
//			bool debug=(rev==0 && now=="abc" && i==0);
			pair<int,pair<int,string> > o=check(now,(rev?a[i]:ra[i]),rev);
			if(o.first==false) continue;
			if(!(dp[o.second.first].find(o.second.second)==dp[o.second.first].end()) && dp[o.second.first][o.second.second]<=cost+::cost[i]) continue;
			dp[o.second.first][o.second.second]=cost+::cost[i];
			squ.insert(mp(dp[o.second.first][o.second.second],o.second));
		}
	}
	cout<<-1<<endl;
	return 0;
}


Compiler output:
In file included from /usr/include/c++/14/random:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:179,
                 from a.cc:248:
/usr/include/c++/14/bits/random.tcc:1364:40: error: macro "ceil" requires 2 arguments, but only 1 given
 1364 |                     __x = std::ceil(__y);
      |                                        ^
a.cc:87:9: note: macro "ceil" defined here
   87 | #define ceil(a,b) ((a-1)/b+1)
      |         ^~~~
/usr/include/c++/14/bits/random.tcc:1386:40: error: macro "ceil" requires 2 arguments, but only 1 given
 1386 |                     __x = std::ceil(__y);
      |                                        ^
a.cc:87:9: note: macro "ceil" defined here
   87 | #define ceil(a,b) ((a-1)/b+1)
      |         ^~~~
/usr/include/c++/14/bits/chrono.h:408:7: error: expected unqualified-id before 'const'
  408 |       ceil(const duration<_Rep, _Period>& __d)
      |       ^~~~
/usr/include/c++/14/bits/chrono.h:408:7: error: expected ')' before 'const'
a.cc:87:20: note: to match this '('
   87 | #define ceil(a,b) ((a-1)/b+1)
      |                    ^
/usr/include/c++/14/bits/chrono.h:408:7: error: expected ')' before 'const'
  408 |       ceil(const duration<_Rep, _Period>& __d)
      |       ^~~~
a.cc:87:19: note: to match this '('
   87 | #define ceil(a,b) ((a-1)/b+1)
      |                   ^
In file included from /usr/include/c++/14/chrono:41,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:172:
/usr/include/c++/14/bits/chrono.h:467:40: error: 'ceil' has not been declared in 'std::chrono'
  467 |     namespace __detail { using chrono::ceil; }
      |                                        ^~~~
/usr/include/c++/14/bits/chrono.h:1062:7: error: expected unqualified-id before 'const'
 1062 |       ceil(const time_point<_Clock, _Dur>& __tp)
      |       ^~~~
/usr/include/c++/14/bits/chrono.h:1062:7: error: expected ')' before 'const'
a.cc:87:20: note: to match this '('
   87 | #define ceil(a,b) ((a-1)/b+1)
      |                    ^
/usr/include/c++/14/bits/chrono.h:1062:7: error: expected ')' before 'const'
 1062 |       ceil(const time_point<_Clock, _Dur>& __tp)
      |       ^~~~
a.cc:87:19: note: to match this '('
   87 | #define ceil(a,b) ((a-1)/b+1)
      |                   ^
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:174:
/usr/include/c++/14/condition_variable: In member function 'std::cv_status std::condition_variable::wait_until(std::unique_lock<std::mutex>&, const std::chrono::time_point<_Clock, _Duration1>&)':
/usr/include/c++/14/condition_variable:135:29: error: 'ceil' is not a member of 'std::chrono::__detail'
  135 |           chrono::__detail::ceil<__s_dur>(__delta);
      |                             ^~~~
/usr/include/c++/14/condition_variable:135:29: note: suggested alternatives:
In file included from /usr/include/features.h:523,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++config.h:683,
                 from /usr/include/c++/14/bits/requires_hosted.h:31,
                 from /usr/include/c++/14/iostream:38,
                 from a.cc:65:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:192:1: note:   'ceil'
  192 | __MATHCALLX (ceil,, (_Mdouble_ __x), (__const__));
      | ^~~~~~~~~~~
In file included from a.cc:67:
/usr/include/c++/14/cmath:174:5: note:   'std::ceil'
  174 |     ceil(_Tp __x)
      |     ^~~~
/usr/include/c++/14/condition_variable:135:41: error: expected primary-expression before '>' token
  135 |           chrono::__detail::ceil<__s_dur>(__delta);
      |                                         ^
/usr/include/c++/14/condition_variable: In member function 'std::cv_status std::condition_variable::wait_for(std::unique_lock<std::mutex>&, const std::chrono::duration<_Rep1, _Period1>&)':
/usr/include/c++/14/condition_variable:167:45: error: 'ceil' is not a member of 'std::chrono::__detail'
  167 |                           chrono::__detail::ceil<__dur>(__rtime));
      |                                             ^~~~
/usr/include/c++/14/condition_variable:167:45: note: suggested alternatives:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:192:1: note:   'ceil'
  192 | __MATHCALLX (ceil,, (_Mdouble_ __x), (__const__));
      | ^~~~~~~~~~~
/usr/include/c++/14/cmath:174:5: note:   'std::ceil'
  174 |     ceil(_Tp __x)
      |     ^~~~
/usr/include/c++/14/condition_variable:167:55: error: expected primary-expression before '>' token
  167 |                           chrono::__detail::ceil<__dur>(__rtime));
      |                                                       ^
/usr/include/c++/14/condition_variable: In member function 'bool std::condition_variable::wait_for(std::unique_lock<std::mutex>&, const std::chrono::duration<_Rep1, _Period1>&, _Predicate)':
/usr/include/c++/14/condition_variable:179:45: error: 'ceil' is not a member of 'std::chrono::__detail'
  179 |                           chrono::__detail::ceil<__dur>(__rtime),
      |                                             ^~~~
/usr/include/c++/14/condition_variable:179:45: note: suggested alternatives:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:192:1: note:   'ceil'
  192 | __MATHCALLX (ceil,, (_Mdouble_ __x), (__const__));
      | ^~~~~~~~~~~
/usr/include/c++/14/cmath:174:5: note:   'std::ceil'
  174 |     ceil(_Tp __x)
      |     ^~~~
/usr/include/c++/14/condition_variable:179:55: error: expected primary-expression before '>' token
  179 |                           chrono::__detail::ceil<__dur>(__rtime),
      |                                                       ^
In file included from /usr/include/c++/14/future:45,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:176:
/usr/include/c++/14/bits/atomic_futex.h: In member function 'bool std::__atomic_futex_unsigned<_Waiter_bit>::_M_load_when_equal_for(unsigned int, std::memory_order, const std::chrono::duration<_Rep, _Period>&)':
/usr/include/c++/14/bits/atomic_futex.h:227:58: error: 'ceil' is not a member of 'std::chrono::__detail'
  227 |                     __clock_t::now() + chrono::__detail::ceil<__dur>(__rtime));
      |                                                          ^~~~
/usr/include/c++/14/bits/atomic_futex.h:227:58: note: suggested alternatives:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:192:1: note:   'ceil'
  192 | __MATHCALLX (ceil,, (_Mdouble_ __x), (__const__));
      | ^~~~~~~~~~~
/usr/include/c++/14/cmath:174:5: note:   'std::ceil'
  174 |     ceil(_Tp __x)
      |     ^~~~
/usr/include/c++/14/bits/atomic_futex.h:227:68: error: expected primary-expression before '>' token
  227 |                     __clock_t::now() + chrono::__detail::ceil<__dur>(__rtime));
      |                                                                    ^
/usr/include/c++/14/bits/atomic_futex.h: In member function 'bool std::__atomic_futex_unsigned<_Waiter_bit>::_M_load_when_equal_until(unsigned int, std::memory_order, const std::chrono::time_point<_Clock, _Duration>&)':
/usr/include/c++/14/bits/atomic_futex.h:241:33: error: 'ceil' is not a member of 'std::chrono::__detail'
  241 |               chrono::__detail::ceil<__clock_t::duration>(__delta);
      |                                 ^~~~
/usr/include/c++/14/bits/atomic_futex.h:241:33: note: suggested alternatives:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:192:1: note:   'ceil'
  192 | __MATHCALLX (ceil,, (_Mdouble_ __x), (__const__));
      | ^~~~~~~~~~~
/usr/include/c++/14/cmath:174:5: note:   'std::ceil'
  174 |     ceil(_Tp __x)
      |     ^~~~
/usr/include/c++/14/bits/atomic_futex.h:241:57: error: expected primary-expression before '>' token
  241 |               chrono::__detail::ceil<__clock_t::duration>(__delta);
      |                                                         ^
/usr/include/c++/14/bits/random.tcc: In member function 'std::poisson_distribution<_IntType>::result_type std::poisson_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&, const param_type&)':
/usr/include/c++/14/bits/random.tcc:1364:32: error: cannot resolve overloaded function 'ceil' based on conversion to type 'double'
 1364 |                     __x = std::ceil(__y);
      |                                ^~~~
/usr/include/c++/14/bits/random.tcc:1386:32: error: cannot resolve overloaded function 'ceil' based on conversion to type 'double'
 1386 |                     __x = std::ceil(__y);
      |                                ^~~~