Toy Shopping

Bessie wants to buy some toys. She has saved her allowance for years and has a huge stash of cash, but she is frugal and wants the best value for her money. She has decided to buy exactly three different toys out of the $N$ ($3 \le N \le 25{,}000$) toys on offer.

Toy $i$ gives Bessie $J_i$ ($0 \le J_i \le 1{,}000{,}000$) microbundles of joy and costs $P_i$ ($0 < P_i \le 100{,}000{,}000$). Bessie has enough money to buy any three toys she likes.

Bessie wants to maximize the total of her happy-frugal metric — defined as $J_i / P_i$ (joy divided by price) — over the three toys she picks. Help her decide which toys to buy. The answer is guaranteed to be unique.

For example, suppose six toys are on offer, with the following happy-frugal metrics:

  i    Joy    Price    Happy-Frugal Metric
  -    ---    -----    -------------------
  1      0      521    0.00000
  2    442      210    2.10476...
  3    119      100    1.19000
  4    120      108    1.11111...
  5    619      744    0.83198...
  6     48       10    4.80000

Bessie would choose toy 6 (metric 4.80), toy 2 (metric 2.10), and toy 3 (metric 1.19).

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: line $i+1$ contains two space-separated integers $J_i$ and $P_i$.

• Line 1: the total price Bessie has to pay (the sum of the prices of the three chosen toys).
• Lines 2 to 4: the 1-based indices of the three toys Bessie should buy, one per line, in descending order of the happy-frugal metric.