사탕

당신과 친구가 큰 사탕 봉지를 함께 나눠 먹으려고 합니다. 두 사람 모두 날씬함을 유지하고 싶어서, 모든 사탕을 두 그룹으로 나누되 두 그룹의 총 열량이 최대한 비슷해지도록 공평하게 나누려고 합니다.

봉지에는 $N$가지 종류의 사탕이 들어 있습니다. $i$번째 종류의 사탕은 $k_i$개가 있으며, 그 종류의 사탕 한 개당 열량은 $c_i$입니다. 각 사탕 한 개를 두 그룹 중 하나에 배정합니다(같은 종류의 사탕이라도 서로 다른 그룹에 나누어 넣을 수 있습니다). 두 그룹의 총 열량 차이가 될 수 있는 가장 작은 값을 구하세요.

첫째 줄에 사탕 종류의 수 $N$이 주어집니다 ($1 \le N \le 100$).

다음 $N$개의 줄에는 각각 두 정수 $k_i$와 $c_i$가 주어집니다. $k_i$는 그 종류의 사탕 개수 ($1 \le k_i \le 500$), $c_i$는 그 종류의 사탕 한 개당 열량 ($1 \le c_i \le 200$)입니다.

두 그룹의 총 열량 차이의 최솟값을 정수 하나로 출력합니다.

예제에서는 한 그룹이 $100$ 열량짜리 사탕 두 개(합 $200$)를 가져가고, 다른 그룹이 나머지 사탕(합 $126$)을 가집니다. 두 그룹의 차이는 $200 - 126 = 74$이며, 이것이 가능한 최소 차이입니다.