小 X 开了一家糖果店，售卖 n 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 i (1 \le i \le n) 种糖果，购买第一颗的价格为 x_i 元，第二颗为 y_i 元，第三颗又变回 x_i 元，第四颗则为 y_i 元，以此类推。

小 R 带了 m 元钱买糖果。小 R 不关心糖果的种类，只想到得到数量尽可能多的糖果。你需要帮助小 R 求出，m 元钱能购买的糖果数量的最大值。

输入的第一行包含两个正整数 n, m，代表糖果的种类数和小 R 的钱数。

输入的第 i+1 (1 \le i \le n) 行包含两个正整数 x_i, y_i，分别表示购买第 i 种糖果时第奇数颗的价格和第偶数颗的价格。

输出一行一个非负整数，表示 m 元钱能购买的糖果数量的最大值。

【样例 1 解释】

小 R 可以购买 4 颗第一种糖果，共花费 4 + 1 + 4 + 1 = 10 元。

【样例 2 解释】

小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 1 + 2 + 12 = 15 元。

【样例 3】

该样例满足测试点 6 的约束条件。

【样例 4】

输入：

10 20
19 17
17 16
7 18
8 15
11 3
19 16
3 6
7 18
2 15
1 9
输出
5

该样例满足测试点 8,9 的约束条件。

【样例 5】

输入：

10 20
12 19
12 15
15 5
9 17
2 3
9 18
15 8
17 16
7 14
17 7
输出：
8

该样例满足测试点 11,12 的约束条件。

【样例 6】

输入：

100 100
75 75
81 81
40 40
34 34
90 90
100 100
98 98
60 60
58 58
7 7
54 54
45 45
46 46
11 11
65 65
95 95
42 42
40 40
3 3
14 14
46 46
70 70
40 40
27 27
21 21
84 84
69 69
9 9
90 90
91 91
10 10
29 29
54 54
87 87
42 42
8 8
60 60
17 17
19 19
17 17
65 65
11 11
7 7
83 83
1 1
77 77
51 51
35 35
61 61
51 51
97 97
51 51
25 25
16 16
47 47
7 7
76 76
25 25
30 30
96 96
44 44
72 72
40 40
73 73
98 98
4 4
69 69
86 86
45 45
30 30
33 33
9 9
100 100
30 30
37 37
63 63
41 41
58 58
1 1
81 81
29 29
62 62
32 32
28 28
36 36
65 65
48 48
2 2
25 25
21 21
75 75
57 57
63 63
4 4
5 5
3 3
96 96
14 14
63 63
8 8
输出：
100

该样例满足测试点 13 的约束条件。

【样例 7】

输入

100 100
21 5
97 88
98 89
20 12
91 21
85 68
47 6
65 29
25 13
95 25
17 10
45 33
26 13
27 23
75 59
94 66
26 12
63 34
61 17
97 73
51 19
59 58
65 57
62 16
97 7
72 40
53 49
45 1
45 29
100 13
59 54
73 63
28 3
82 11
52 1
37 4
76 35
93 56
80 72
77 66
69 31
94 68
98 9
8 1
70 29
59 22
30 7
88 43
93 60
54 12
77 34
97 87
75 35
37 11
20 1
56 25
91 15
72 65
89 80
50 5
47 22
76 21
72 12
90 69
82 28
54 34
99 34
31 2
70 54
40 8
100 96
95 61
81 36
79 60
74 60
95 22
80 54
68 67
83 67
77 65
78 21
90 39
94 24
16 7
89 46
98 76
93 45
97 48
69 38
75 20
40 3
100 23
27 2
46 8
78 64
59 12
19 4
8 3
100 94
78 51
输出
22

该样例满足测试点 17,18 的约束条件。

【数据范围】

对于所有测试数据，均有：