UTS Open '18 P4 - Ianine's Lil Lab

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

UTS needs a computer lab for the new building at 30 Humbert Street, and Mr. Ianine is in charge of buying new computers. Each desktop computer needs a keyboard and a monitor. Luckily, Mr. Ianine has N (1 \le N \le 2\cdot 10^5) coupons. The i^{th} coupon lets him buy either K_i keyboards or M_i monitors, but it cannot be used for both keyboards and monitors.

Being the fair person that he is, Mr. Ianine wants all coupons to be treated equally. He defines the value of the i^{th} coupon as V_i = K_i + M_i, and he must ensure that all the coupons he uses have the same value.

After using the coupons at the store, Mr. Ianine pairs up his keyboards and monitors. Each pair will be used for one working computer, and any extra unpaired keyboards and monitors are kept away in the IT room. What is the maximum number of working computers that he can get?

Input Specification

The first line contains N (1 \le N \le 2\cdot 10^5), the number of coupons that Mr. Ianine has.

The next N lines contain two integers K_i and M_i, the number of keyboards and monitors that the i^{th} coupon allows him to buy. It is guaranteed that K_i, M_i \ge 0 and 0 \le V_i \le 10^5.

Output Specification

Output the maximum number of working computers that Mr. Ianine can get, by using coupons of the same value.


Subtask 1 [10%]

0 \le V_i \le 2 for all i.

Subtask 2 [30%]

1 \le N \le 20.

Subtask 3 [60%]

No additional constraints.

Sample Input

1 4
7 1
0 5
4 1
4 4
2 3

Sample Output


Explanation for Sample Output

Mr. Ianine should use the coupons with value 5. He should use coupons 4 and 6 to buy 4+2=6 keyboards, and coupons 1 and 3 to buy 4+5=9 monitors. Then he will have 6 working computers.


There are no comments at the moment.