P2036 [COCI 2008/2009 #2] PERKET

# Description Perket is a popular dish. To make a good Perket, the chef must choose the ingredients carefully to achieve the most balanced flavor while keeping the traditional taste. You have $n$ available ingredients. For each ingredient, we know its sourness $s$ and bitterness $b$. When we add ingredients, the total sourness is the product of the sourness values of the chosen ingredients; the total bitterness is the sum of the bitterness values of the chosen ingredients. It is well known that a good dish should be well balanced, so we want to choose a subset of ingredients that minimizes the absolute difference between the total sourness and the total bitterness. Also, we must add at least one ingredient, because no dish is made with only water.

Perket is a popular dish. To make a good Perket, the chef must choose the ingredients carefully to achieve the most balanced flavor while keeping the traditional taste. You have $n$ available ingredients. For each ingredient, we know its sourness $s$ and bitterness $b$. When we add ingredients, the total sourness is the product of the sourness values of the chosen ingredients; the total bitterness is the sum of the bitterness values of the chosen ingredients. It is well known that a good dish should be well balanced, so we want to choose a subset of ingredients that minimizes the absolute difference between the total sourness and the total bitterness. Also, we must add at least one ingredient, because no dish is made with only water. # Description

The first line contains an integer $n$, the number of available ingredient types. The next $n$ lines each contain $2$ integers $s_i$ and $b_i$, the sourness and bitterness of the $i$-th ingredient.

Output a single integer: the minimum possible absolute difference between the total sourness and the total bitterness.

For the third sample, choose the last three ingredients. Then the total sourness is $2 \times 3 \times 4 = 24$, the total bitterness is $6+8+9=23$, and the difference is $1$. Constraints - For $100\%$ of the testdata, $1 \leq n \leq 10$, and the total sourness and the total bitterness obtained by using all available ingredients are less than $1 \times 10^9$. Notes - This problem is worth $70$ points. - Translated from [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) PERKET, translator @[mnesia](https://www.luogu.com.cn/user/115711). Translated by ChatGPT 5