この問題は動的計画法によって解く事ができます。

bool型の\(2\) 次元配列 \(dp[i][j]\) \((0\leq i\leq N, 0\leq j\leq X)\) を、「\(A_1\) 円硬貨を \(B_1\) 枚, \(A_2\) 円硬貨を \(B_2\) 枚, \(\ldots\), \(A_i\) 円硬貨を \(B_i\) 枚を用いてちょうど \(j\) 円を払えるならば True , 払えないならば False」として定め、これを \(i=0,1,\ldots,N\) の順で求める事を考えます。
問題に対する答えは、\(dp[N][X]\) が True ならば Yes、False ならば No となります。

まず、\(i=0\) の場合について、高橋君は \(1\) 枚も硬貨を持っていないため、\(dp[0][0]=\) True , \(j>0\) のとき \(dp[0][j]=\) False です。

さて、\(dp[i-1][j]\) \((0\leq j\leq X)\) が求まっているとき、\(dp[i][j]\) を求める事を考えます。
\(A_i\) 円硬貨は\(0\) 枚以上 \(B_i\) 枚以下の範囲で自由に使えるので、 \(0\leq k\leq B_i\) をみたす整数 \(k\) であって、\(j-kA_i\geq 0\) かつ \(dp[i-1][j-kA_i]=\) True であるようなものが \(1\) つでも存在すれば \(dp[i][j]\) は True となり、そうでないならば False となります。 すなわち、

\[ dp[i][j]=dp[i-1][j]\lor dp[i-1][j-A_i]\lor dp[i-1][j-2A_i]\lor \cdots\lor dp[i-1][j-B_iA_i]\quad (ただし、j'<0 ならば dp[i-1][j']=\text{False}) \]

となります。

これをナイーブに実装すると, 計算量は 各\(i\) について \(O(B_iX)\) となるため全体で \(O((\displaystyle\sum_{i=1}^N B_i)X)\) であり、今回の制約下で十分高速に動きます。よって、この問題を解く事ができました。

\(O(NX)\) 解法について

なお、この問題には \(O(NX)\) 解法が存在します。 基本的な方針は上記の方針と同じですが、\(dp[i][j]\) を求める前に各\(j\) について、
\(dp'[i-1][j]=\) ( \(j'=j,j-A_i,j-2A_i,\ldots\) のうち \(dp[i-1][j']=\)True であるような最大の\(j'\) )(存在しなければ\(-\infty\)) を計算します。

\(dp'[i-1][j]\)は \(dp[i-1][j]=\)True ならば \(dp'[i-1][j]=j\), そうでなければ \(dp'[i-1][j]=dp'[i-1][j-A_i]\) として\(j\) が小さい方から順に\(O(1)\) で計算する事ができます。 さらに、本解法で求めた漸化式から, \(dp[i][j]\)は\(dp'[i-1][j]\geq j-A_iB_i\) ならば True, そうでないならばFalse としてこれも \(O(1)\) で計算する事ができます。
よって、各\(i\) について \(O(X)\), 全体で \(O(NX)\) で解く事ができました。

c++ による実装例 (本解法):

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n,x;
	int a[50];
	int b[50];
	bool dp[51][10001];

	cin>>n>>x;
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];

	for(int i=0;i<=n;i++)for(int j=0;j<=x;j++)dp[i][j]=false;
	dp[0][0]=true;
	for(int i=0;i<n;i++){
		for(int j=0;j<=x;j++){
			for(int k=0;k<=b[i];k++){
				if(j>=a[i]*k){
					if(dp[i][j-a[i]*k])dp[i+1][j]=true;
				}
			}
		}
	}

	if(dp[n][x])cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

c++ による実装例(\(O(NX)\)解法) :

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n,x;
	int a[50];
	int b[50];
	bool dp[10001]; //配列は使い回し
	int mx[100];

	cin>>n>>x;
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];

	for(int i=0;i<=x;i++)dp[i]=false;
	dp[0]=true;
	for(int i=0;i<n;i++){
		for(int j=0;j<a[i];j++)mx[j]=-10000; //-a[i]*b[i]未満なら良い
		for(int j=0;j<=x;j++){
			if(dp[j])mx[j%a[i]]=j;
			if(mx[j%a[i]]>=j-(a[i]*b[i]))dp[j]=true;
			else dp[j]=false;
		}
	}

	if(dp[x])cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}