stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <queue>

#include <iomanip>



using namespace std;

typedef long long ll;



int main() {

	int H, W, N;

	int sr, sc;

	cin >> H >> W >> N;

	cin >> sr >> sc;

	getchar();

	string s, t;

	getline(cin, s);

	getline(cin, t);

	int position = sc;

	for (int i = 0; i < N; i++) {

		if (s[i] == 'R') position++;

		if (position > W) { cout << "NO" << endl; return 0; }

		if (t[i] == 'L' && position > 1) position--;

	}

	position = sc;

	for (int i = 0; i < N; i++) {

		if (s[i] == 'L') position--;

		if (position < 1) { cout << "NO" << endl; return 0; }

		if (t[i] == 'R' && position <W) position++;

	}

	position = sr;

	for (int i = 0; i < N; i++) {

		if (s[i] == 'U') position--;

		if (position < 1) { cout << "NO" << endl; return 0; }

		if (t[i] == 'D' && position<H) position++;

	}

	position = sr;

	for (int i = 0; i < N; i++) {

		if (s[i] == 'D') position++;

		if (position > H) { cout << "NO" << endl; return 0; }

		if (t[i] == 'U'&& position > 1) position--;

	}

	cout << "YES" << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



char s1[200001],s2[200001];

int main(){

	int n,m,k;

	int x,y;

	scanf("%d%d%d",&n,&m,&k);

	scanf("%d%d%s%s",&x,&y,s1+1,s2+1);

	int l1=1,r1=n,l2=1,r2=m;

	for(int i=k;i;i--){

		if(s2[i]=='U')r1=min(n,r1+1);

		if(s2[i]=='D')l1=max(1,l1-1);

		if(s2[i]=='L')r2=min(m,r2+1);

		if(s2[i]=='R')l2=max(1,l2-1);

		if(s1[i]=='U')l1++;

		if(s1[i]=='D')r1--;

		if(s1[i]=='L')l2++;

		if(s1[i]=='R')r2--;

		//printf("%d %d %d %d\n",l1,r1,l2,r2);

		if(l1>r1||l2>r2){

			printf("NO\n");

			return 0;

		}

	}

	if(x>=l1&&x<=r1&&y>=l2&&y<=r2)

		printf("YES\n");

	else printf("NO\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdlib>



using namespace std;



char s[200005], t[200005];

int x, y, n, l, c;



void incearcaSus();

void incearcaJos();

void incearcaDreapta();

void incearcaStanga();



int main()

{

    int i;



    cin >> l >> c >> n;

    cin >> x >> y;

    int cx=x, cy=y;

    cin >> s >> t;

    x = cx; y = cy;

    incearcaSus();

    x = cx; y = cy;

    incearcaJos();

    x = cx; y = cy;

    incearcaDreapta();

    x = cx; y = cy;

    incearcaStanga();

    cout << "YES\n";

    return 0;

}



void incearcaSus()

{

    for (int i=0;i<n;i++)

    {

        if (s[i] == 'U')

            x--;

        if (x == 0)

        {

            cout << "NO\n";

            exit(0);

        }

        if (t[i] == 'D' && x < l)

            x++;

    }

}

void incearcaJos()

{

    for (int i=0;i<n;i++)

    {

        if (s[i] == 'D')

            x++;

        if (x == l+1)

        {

            cout << "NO\n";

            exit(0);

        }

        if (t[i] == 'U' && x > 1)

            x--;

    }

}

void incearcaStanga()

{

    for (int i=0;i<n;i++)

    {

        if (s[i] == 'L')

            y--;

        if (y == 0)

        {

            cout << "NO\n";

            exit(0);

        }

        if (t[i] == 'R' && y < c)

            y++;

    }

}

void incearcaDreapta()

{

    for (int i=0;i<n;i++)

    {

        if (s[i] == 'R')

            y++;

        if (y == c+1)

        {

            cout << "NO\n";

            exit(0);

        }

        if (t[i] == 'L' && y > 1)

            y--;

    }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



char s1[200001],s2[200001];

int main(){

	int n,m,k;

	int x,y;

	scanf("%d%d%d",&n,&m,&k);

	scanf("%d%d%s%s",&x,&y,s1+1,s2+1);

	int l1=1,r1=n,l2=1,r2=m;

	for(int i=k;i;i--){

		if(s2[i]=='U')r1=min(n,r1+1);

		if(s2[i]=='D')l1=max(1,l1-1);

		if(s2[i]=='L')r2=min(m,r2+1);

		if(s2[i]=='R')l2=max(1,l2-1);

		if(s1[i]=='U')l1++;

		if(s1[i]=='D')r1--;

		if(s1[i]=='L')l2++;

		if(s1[i]=='R')r2--;

		//printf("%d %d %d %d\n",l1,r1,l2,r2);

		if(l1>r1||l2>r2){

			printf("NO\n");

			return 0;

		}

	}

	if(x>=l1&&x<=r1&&y>=l2&&y<=r2)

		printf("YES\n");

	else printf("NO\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



const int N=int(2e5)+10;

int H,W,n,sr,sc,suf[N];

char s[N],t[N];

bool check(char a,char b,int dis,int lim) {

	suf[n+1]=0;

	int sum=0;

	for (int i=n;i>=1;--i) {

		suf[i]=suf[i+1];

		if (s[i]==b) {

			suf[i]=std::min(suf[i],sum-1);

			--sum;

		}

		if (t[i]==a) {

			if (sum<0) ++sum;

		}

	}

	int pos=dis;

	for (int i=1;i<=n;++i) {

		if (s[i]==a) ++pos;

		if (pos>lim) return 0;

		if (t[i]==b) {

			if (pos-1+suf[i+1]>=1) --pos;

		}

	}

	return 1;

}

int main() {

	scanf("%d%d%d%d%d",&H,&W,&n,&sr,&sc);

	scanf("%s",s+1);

	scanf("%s",t+1);

	if (!check('D','U',sr,H)||!check('U','D',H-sr+1,H)||!check('R','L',sc,W)||!check('L','R',W+1-sc,W))

		puts("NO");

	else puts("YES");

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



char s1[200001],s2[200001];

int main(){

	int n,m,k;

	int x,y;

	scanf("%d%d%d",&n,&m,&k);

	scanf("%d%d%s%s",&x,&y,s1+1,s2+1);

	int l1=1,r1=n,l2=1,r2=m;

	for(int i=k;i;i--){

		if(s2[i]=='U')r1=min(n,r1+1);

		if(s2[i]=='D')l1=max(1,l1-1);

		if(s2[i]=='L')r2=min(m,r2+1);

		if(s2[i]=='R')l2=max(1,l2-1);

		if(s1[i]=='U')l1++;

		if(s1[i]=='D')r1--;

		if(s1[i]=='L')l2++;

		if(s1[i]=='R')r2--;

		//printf("%d %d %d %d\n",l1,r1,l2,r2);

		if(l1>r1||l2>r2){

			printf("NO\n");

			return 0;

		}

	}

	if(x>=l1&&x<=r1&&y>=l2&&y<=r2)

		printf("YES\n");

	else printf("NO\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <cmath>

using namespace std;



const int maxn = 2e5+100;



int h,w,n,x,y;

char s1[maxn];

char s2[maxn];

int ans=0;

int L[maxn],R[maxn],U[maxn],D[maxn];

int main()

{

	cin>>h>>w>>n;

	cin>>x>>y;

	scanf("%s",s1+1);

	scanf("%s",s2+1);

	ans=0;

	/*for(int i=1;i<=n;i++)

	{

		if(s[i]=='L') L[i]++;

		if(s[i]=='R') R[i]++;

		if(s[i]=='U') U[i]++;

		if(s[i]=='D') D[i]++;

		L[i]+=L[i-1];R[i]+=R[i-1];

		U[i]+=U[i-1];D[i]+=D[i-1];

	}*/

	for(int i=1;i<=n;i++)

	{

		if(s1[i]=='L') ans++;

		if(ans>=y){

			cout<<"NO"<<endl;

			return 0;

		}

		if(s2[i]=='R')

		{

			if(ans<0&&abs(ans-1)==w-y+1) continue;

			ans--;

		} 

	}

	ans=0;

	//cout<<"111111"<<endl;

	for(int i=1;i<=n;i++)

	{

		if(s1[i]=='U') ans++;

		if(ans>=x){

			cout<<"NO"<<endl;

			return 0;

		}

		if(s2[i]=='D')

		{

			if(ans<0&&abs(ans-1)==h-x+1) continue;

			ans--;

		} 

	}

	//cout<<"22222222222"<<endl;

	ans=0;

	for(int i=1;i<=n;i++)

	{

		if(s1[i]=='R') ans++;

		if(ans>=w-y+1){

			cout<<"NO"<<endl;

			return 0;

		}

		if(s2[i]=='L')

		{

			if(ans<0&&abs(ans-1)==y) continue;

			ans--;

		} 

	}

	//cout<<"333333333333333"<<endl;

	ans=0;

	for(int i=1;i<=n;i++)

	{

		if(s1[i]=='D') ans++;

		if(ans>=h-x+1){

			cout<<"NO"<<endl;

			return 0;

		}

		if(s2[i]=='U')

		{

			if(ans<0&&abs(ans-1)==x) continue;

			ans--;

		} 

	}

	//cout<<"4444444444444444444444444444444444444"<<endl;

	cout<<"YES"<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

using namespace std;

const int N = 2e5 + 5;

char s[N], t[N];



int main()

{

    int h, w, n, x, y;

    scanf("%d%d%d%d%d%s%s", &h, &w, &n, &x, &y, &s, &t);



    bool flag = true;

    int l = y, r = y, u = x, d = x;

    for (int i = 0; i < n; i ++)

    {

        switch (s[i])

        {

        case 'U': u--; break;

        case 'D': d++; break;

        case 'R': r++; break;

        case 'L': l--; break;

        }

        if (u == 0 || d == h + 1 || l == 0 || r == w + 1)

        {

            flag = false;

            break;

        }

        switch (t[i])

        {

        case 'U': if(d != 1) d--; break;

        case 'D': if(u != h) u++; break;

        case 'R': if(l != w) l++; break;

        case 'L': if(r != 1) r--; break;

        }

    }

    if (flag) printf("YES\n");

    else printf("NO\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <map>

#include <vector>

#include <tuple>

#include <algorithm>

using namespace std;



int a[200010];

int prv[200010],nxt[200010];

bool win[200010];



int main(void){

	int n,m,q;

	cin >> n >> m >> q;



	for(int i=0;i<n;++i){

		prv[i]=(i+n-1)%n,nxt[i]=(i+1)%n;win[i]=true;

	}

	int cur=0;

	for(int i=0;i<m;++i){

		cin >> a[i];

		if(a[i]&1){

			for(int j=0;j<a[i];++j) cur=prv[cur];

		}else{

			for(int j=0;j<a[i];++j) cur=nxt[cur];

		}

		win[cur]=false;

		nxt[prv[cur]]=nxt[cur];

		prv[nxt[cur]]=prv[cur];

		cur=nxt[cur];

	}



	for(int i=0;i<q;++i){

		int in;

		cin >> in;

		cout << win[in] << endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#define rep(i,n) for(i=0;i<n;++i)

int a[1<<18],v[1<<18][3],n,m,q,c,i,j;

main(){scanf("%d%d%d",&n,&m,&q);rep(i,n)rep(j,2)v[i][j]=(i+n+1-2*j)%n;rep(i,m){scanf("%d",a+i);rep(j,a[i])c=v[c][a[i]&1];v[c][2]=1;rep(j,2)v[v[c][j^1]][j]=v[c][j];c=v[c][0];}rep(i,q)scanf("%d",&c),printf("%d\n",1-v[c][2]);}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cmath>

#include <cstring>

#include <utility>

#include <queue>

#include <vector>

#include <string>

#include <set>

#include <functional>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long LL;

typedef pair<int,int> P;

struct Node {

	int val;

	Node *prev;

	Node *next;

	Node(int v) {

		val=v;

		prev=next=NULL;

	}

};

Node *head=NULL,*tail=NULL;

void add(int val) {

	Node *New=new Node(val);

	if(head==NULL) {

		head=tail=New;

	}else {

		tail->next=New;

		New->prev=tail;

		tail=New;

	}

}

void del(Node *node) {

	if(node->prev!=NULL) {

		node->prev->next=node->next;

	}else {

		head=node->next;

	}

	if(node->next!=NULL) {

		node->next->prev=node->prev;

	}else {

		tail=node->prev;

	}

	delete node;

}

bool OK[200000];

int main() {

	int N,M,Q;

	scanf("%d %d %d",&N,&M,&Q);

	for(int i=0;i<N;i++) {

		add(i);

	}

	Node *cur=head;

	for(int i=0;i<M;i++) {

		int a;

		scanf("%d",&a);

		if(a&1) {

			for(int i=0;i<a;i++) {

				cur=cur->prev;

				if(cur==NULL) cur=tail;

			}

			Node *tmp=cur;

			cur=cur->next;

			if(cur==NULL) cur=head;

			del(tmp);

		}else {

			for(int i=0;i<a;i++) {

				cur=cur->next;

				if(cur==NULL) cur=head;

			}

			Node *tmp=cur;

			cur=cur->next;

			if(cur==NULL) cur=head;

			del(tmp);

		}

	}

	for(Node *cur=head;cur!=NULL;cur=cur->next) {

		OK[cur->val]=1;

	}

	for(int i=0;i<Q;i++) {

		int q;

		scanf("%d",&q);

		printf("%d\n",OK[q]);

	}

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <string>

#include <utility>

#include <set>

#include <queue>

#include <algorithm>

using namespace std;

int nxt[200000], prv[200000];

bool OK[200000];

int main() {

	int N, M, Q;

	scanf("%d %d %d", &N, &M, &Q);

	for (int i = 0; i < N; i++) {

		nxt[i] = (i + 1) % N;

		prv[i] = (i - 1 + N) % N;

	}

	int cur = 0;

	for (int i = 0; i < M; i++) {

		int a;

		scanf("%d", &a);

		if (a & 1) {

			for (int j = 0; j < a; j++) {

				cur = prv[cur];

			}

		}

		else {

			for (int j = 0; j < a; j++) {

				cur = nxt[cur];

			}

		}

		nxt[prv[cur]] = nxt[cur];

		prv[nxt[cur]] = prv[cur];

		cur = nxt[cur];

	}

	OK[cur] = 1;

	int tmp = cur;

	for (cur = nxt[cur]; cur != tmp; cur = nxt[cur]) {

		OK[cur] = 1;

	}

	for (int i = 0; i < Q; i++) {

		int q;

		scanf("%d", &q);

		printf("%d\n", OK[q]);

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int N, M, Q, p, r, a, prv[200007], nxt[200007];

int main() {

	cin >> N >> M >> Q;

	for (int i = 0; i < N; i++) prv[i] = (i + N - 1) % N, nxt[i] = (i + 1) % N;

	for (int i = 0; i < M; i++) {

		cin >> a;

		for (int j = 0; j < a; j++) p = a % 2 ? prv[p] : nxt[p];

		nxt[prv[p]] = nxt[p], prv[nxt[p]] = prv[p];

		r = nxt[p], prv[p] = nxt[p] = -1, p = r;

	}

	for (int i = 0; i < Q; i++) cin >> a, cout << (prv[a] != -1 ? 1 : 0) << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

int N, M, Q, p, r, a, prv[200007], nxt[200007];

int main() {

	scanf("%d%d%d", &N, &M, &Q);

	for (int i = 0; i < N; i++) prv[i] = (i + N - 1) % N, nxt[i] = (i + 1) % N;

	for (int i = 0; i < M; i++) {

		scanf("%d", &a);

		for (int j = 0; j < a; j++) p = a % 2 ? prv[p] : nxt[p];

		nxt[prv[p]] = nxt[p], prv[nxt[p]] = prv[p];

		r = nxt[p], prv[p] = nxt[p] = -1, p = r;

	}

	for (int i = 0; i < Q; i++) scanf("%d", &a), puts(prv[a] != -1 ? "1" : "0");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "bits/stdc++.h"

using namespace std;

typedef pair<int,int> pii;

#define rep(i,n) for(int i=0;i<(int)(n);i++)

#define all(a)  (a).begin(),(a).end()

#define pb push_back

#define INF 1<<30

#define MAX_V 200



struct edge{int to,cap,rev;};



vector<edge> G[10000];

bool used[10000];

void add_edge(int from,int to,int cap){

    G[from].pb((edge){to,cap,(int)G[to].size()});

    G[to].pb((edge){from,0,(int)(G[from].size())-1});

}



// ?¢?????????????DFS??§??¢???

int dfs(int v, int t, int f) {

    if (v == t) return f;

    used[v] = true;

    for (int i = 0; i < G[v].size(); i++) {

        edge &e = G[v][i];

        if (!used[e.to] && e.cap > 0) {

            int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) {

                e.cap -= d;

                G[e.to][e.rev].cap += d;

                return d;

            }

        }

    }

    return 0;

}

// s??????t???????????§???????±???????

int max_flow(int s, int t) {

    int flow = 0; for (;;) {

        memset(used, 0, sizeof(used)); int f = dfs(s, t, INF);

        if (f == 0) return flow;

        flow += f;

    }

}



int main(){

    int v,e;

    cin>>v>>e;

    rep(i,e){

        int uu,vv,cc;

        cin>>uu>>vv>>cc;

        add_edge(uu,vv,cc);

    }

    cout<<max_flow(0,v-1)<<endl;

}

// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)

#define all(a)  (a).begin(),(a).end()

#define pb push_back

#define INF (1e9+1)

//#define INF (1LL<<59)



#define MAX_V 100





// ????????¨???

struct edge{int to,cap,rev;};



vector<edge> G[MAX_V];  //??°???????????????

int level[MAX_V];       //?§??????????????????¢

int iter[MAX_V];        //???????????§????????????



// from??????to?????????????????????cap???????????°?????????????????????

void add_edge(int from,int to,int cap){

	G[from].push_back(  (edge){ to  ,cap,(int)G[to  ].size()   }  );

	G[to  ].push_back(  (edge){ from,0  ,(int)G[from].size()-1 }  );

}



// s????????????????????¢???BFS??§?¨??????????

void bfs(int s){

	rep(i,MAX_V)level[i]=-1;

	queue<int> que;

	level[s]=0;

	que.push(s);

	while(!que.empty()){

		int v=que.front();que.pop();

		

		rep(i,G[v].size()){

			edge &e=G[v][i];

			if(e.cap>0 && level[e.to]<0){

				level[e.to]=level[v]+1;

				que.push(e.to);

			}

		}

	}

}



//?¢?????????????DFS??§??¢???

int dfs(int v,int t,int f){

	if(v==t)return f;

	for(int &i=iter[v];i<G[v].size();i++){

		edge &e=G[v][i];

		if(e.cap>0&&level[v]<level[e.to]){

			int d=dfs(e.to,t,min(f,e.cap));

			if(d>0){

				e.cap-=d;

				G[e.to][e.rev].cap+=d;

				return d;

			}

		}

	}

	return 0;

}



// s??????t???????????§???????±???????

int max_flow(int s,int t){

	int flow=0;

	for(;;){

		bfs(s);

		if(level[t]<0)return flow;

		memset(iter,0,sizeof(iter));

		int f;

		while((f=dfs(s,t,INF))>0){

			flow+=f;

		}

	}

}





int main(){

	int v,e;

	cin>>v>>e;

	rep(i,e){

		int a,b,c;

		cin>>a>>b>>c;

		add_edge(a,b,c);

	}

	cout<<max_flow(0,v-1)<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define INF 1e9

#define MAX_V 10000

using namespace std;



//????????¨????§???????(???????????????????????????)

struct edge{int to, cap, rev;};



vector<edge> G[MAX_V]; //??°???????????£??\?????????

bool used[MAX_V];      //DFS??§?????§??????????????????????????°



//from??????to??????????????????cap???????????°?????????????????????

void add_edge(int from,int to,int cap){

  G[from].push_back((edge){to,cap,G[to].size()});

  G[to].push_back((edge){from,0,G[from].size()-1});  

}





//?¢?????????????DFS??§??¢???

int dfs(int v,int t,int f){

  if(v == t)return f;

  used[v]=true;

  for(int i=0; i<G[v].size() ;i++){

    edge &e = G[v][i];

    if(!used[e.to] && e.cap > 0){

      int d = dfs(e.to ,t , min(f,e.cap));

      if(d > 0){

	e.cap -= d;

	G[e.to][e.rev].cap += d;

	return d;

      }

    }

  }

  return 0;

}



//s??????t???????????§???????±???????

int max_flow(int s,int t){

  int flow = 0;

  for(;;){

    memset(used,0,sizeof(used));

    int f = dfs(s, t, INF);

    if(f == 0)return flow;

    flow += f;

  }

}





int main(){

  int n,m;

  cin>>n>>m;

  for(int i=0;i<m;i++){

    int u,v,c;

    cin>>u>>v>>c;

    add_edge(u,v,c);

  }

  cout<<max_flow(0,n-1)<<endl;



}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define MAX_V 1000

#define INF 1e9

using namespace std;



//????????¨????§???????(???????????????????????????)

struct edge{int to,cap,rev;};

vector<edge> G[MAX_V]; //??°???????????£??\???????????¨???

int level[MAX_V];      //s??????????????¢

int iter[MAX_V];       //???????????§??????????????£??????



//from??????to??????????????????cap???????????°??????????????????

void add_edge(int from,int to,int cap){

  G[from].push_back((edge){to,cap,G[to].size()});

  G[to].push_back((edge){from,0,G[from].size()-1});

}



//s????????????????????¢???BFS??§?¨??????????

void bfs(int s){

  memset(level,-1,sizeof(level));

  queue<int> que;

  level[s] = 0;

  que.push(s);

  while(!que.empty()){

    int v = que.front(); que.pop();

    for(int i=0; i<G[v].size(); i++){

      edge &e = G[v][i];

      if(e.cap > 0 && level[e.to] < 0){

	level[e.to] = level[v] + 1;

	que.push(e.to);

      }

    }

  }

}



//?¢?????????????DFS??§??¢??????

int dfs(int v,int t,int f){

  if(v==t) return f;

  for(int &i= iter[v]; i<G[v].size(); i++){

    edge &e = G[v][i];

    if(e.cap > 0 && level[v] < level[e.to]){

      int d = dfs(e.to, t, min(f, e.cap));

      if(d > 0){

	e.cap -= d;

	G[e.to][e.rev].cap += d;

	return d;

      }

    }

  }

  return 0;

}



//s??????t???????????§???????±???????

int max_flow(int s,int t){

  int flow=0;

  for(;;){

    bfs(s);

    if(level[t] < 0) return flow;

    memset(iter,0,sizeof(iter));

    int f;

    while((f=dfs(s ,t ,INF)) > 0 ) flow += f;

  }

}



int main(){

  int V,E;

  cin>>V>>E;



  for(int i=0;i<E;i++){

    int u,v,c;

    cin>>u>>v>>c;

    add_edge(u,v,c);

  }

  cout <<max_flow(0,V-1)<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm> 

#include <queue>

#include <functional>

#include <map>

#include <string>

using namespace std;

typedef long long ll;



const int INF = 10000000;

int n, ma, mb;

int a[45], b[45], c[45];

int dp[45][405][405];



int rec(int i, int  A, int B){

    if (dp[i][A][B] > 0){

        return dp[i][A][B];

    }



    if (A > 0 && B > 0 && ma*B == mb*A){

        return dp[i][A][B] = 0;

    }



    if (i == n){

        return INF;

    }



    int ret = INF;

    ret = min(ret, rec(i + 1, A, B));



    ret = min(ret, c[i] + rec(i + 1, A + a[i], B + b[i]));

    



    return dp[i][A][B] = ret;

    

}



int main(void){

   

    cin >> n >> ma >> mb;



    for (int i = 0; i < n; i++){

        cin >> a[i] >> b[i] >> c[i];

    }



    for (int i = 0; i < n; i++){

        for (int j = 0; j <= 400; j++){

            for (int k = 0; k <= 400; k++){

                dp[i][j][k] = -1;

            }

        }

    }



    int ans = rec(0, 0, 0);

    

    if (ans >= INF){

        cout << -1 << endl;

    }

    else{

        cout << ans << endl;

    }

    

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <iomanip>

#include <cstring>

#include <algorithm> 

#include <queue>

#include <functional>

#include <map>

#include <vector>

#include <string>

using namespace std;

typedef long long ll;

const int INF = 100000;



int dp[45][405][405];



int main(void){

    int n, a[45], b[45], c[45], ma, mb, suma = 0, sumb = 0;



    cin >> n >> ma >> mb;

    for (int i = 0; i < n; i++){

        cin >> a[i] >> b[i] >> c[i];

        suma += a[i]; sumb += b[i];

    }



    for (int i = 0; i <= suma; i++)

        for (int j = 0; j <= sumb; j++) dp[0][i][j] = INF;



    dp[0][0][0] = 0;



    for (int i = 0; i < n; i++){

        for (int j = 0; j <= suma; j++){

            for (int k = 0; k <= sumb; k++){

                dp[i + 1][j][k] = dp[i][j][k];

                if (a[i] <= j && b[i] <= k) dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j - a[i]][k - b[i]] + c[i]);

            }

        }

    }



    int ans = INF;

    for (int i = 1; i <= suma; i++){

        for (int j = 1; j <= sumb; j++){

            if (ma*j == mb*i) ans = min(ans, dp[n][i][j]);

        }

    }



    if (ans == INF) ans = -1;

    cout << ans << endl;



}

// Fastest known solution for this problem: