Окорочок худеет, и потому вплоть до осени его диета будет состоять только из брокколи, риса и куриной грудки. Окорочок может кушать любое количество брокколи, но на рис и куриную грудку есть ограничения.

До осени у Окорочка будет ровно $$$n$$$ походов в магазин, и для каждого похода известно $$$a_i$$$ — количество сухого риса в граммах — и $$$b_i$$$ — количество сырой куриной грудки в граммах, которые он собирается купить. Также известно, что один приём пищи Окорочка будет состоять из $$$k$$$ граммов риса и грудки в сумме. Но Окорочок решил не смешивать рис и грудку из разных походов в магазин, а потому приём пищи всегда будет иметь один из следующих типов:

• $$$x$$$ граммов риса и $$$y$$$ граммов грудки, которые были куплены в один и тот же поход в магазин, причём $$$x + y = k$$$;
• $$$x_1, x_2, \ldots, x_r$$$ граммов риса ($$$x_1 + x_2 + \ldots + x_r = k$$$), где $$$x_i$$$ — часть от всего риса, купленного в какой-то из походов в магазин;
• $$$y_1, y_2, \ldots, y_r$$$ граммов грудки ($$$y_1 + y_2 + \ldots + y_r = k$$$), где $$$y_i$$$ — часть от всей грудки, купленной в какой-то из походов в магазин.

Например, если у Окорочка будет два похода в магазин, в первый поход он купит 200 граммов риса и 500 граммов куриной грудки, а во второй — 100 граммов риса и 200 граммов куриной грудки, то он сможет приготовить только 2 приёма пищи с $$$k = 400$$$ — например, так:

• первый приём пищи: 100 граммов риса и 300 граммов куриной грудки с первого похода;
• второй приём пищи: 200 оставшихся граммов куриной грудки с первого похода и 200 граммов куриной грудки со второго похода.

Помогите Окорочку определить максимальное количество приёмов пищи, которые он сможет приготовить для себя до осени!