Internet Service Providers

Time limit1sMemory limit128 MB

Summary
Given N and C, find the smallest integer T minimizing/maximizing the quadratic profit N*T*(C-T*N), handling N=0 edge case.
Level

Easy3 of 10

Topics
Math, Implementation, Binary search
Solved
No attempts yet

Problem

A group of NN Internet Service Provider companies (ISPs) share a private communication channel whose maximum capacity is CC traffic units per second. Every ISP pushes the same amount of TT traffic units per second through the channel, and each ISP earns a profit that is directly proportional to T (C−T N)T\,(C - T\,N). The total profit of all NN ISPs is therefore proportional to N T (C−T N)N\,T\,(C - T\,N).

Compute ToptimT_{optim}: the smallest integer value of TT that maximizes this total profit. Here NN, CC, TT, and ToptimT_{optim} are all integers.

When there are no ISPs (N=0N = 0), the total profit is 00 for every TT, and Toptim=0T_{optim} = 0.

Input

The input contains several independent data sets and is read until end of file. Each data set has two integers NN and CC (0≤N,C≤1090 \le N, C \le 10^9), separated by whitespace: the number of ISPs and the channel capacity. The data are guaranteed to be valid.

Output

For each data set, print ToptimT_{optim} on its own line, in the same order as the input. Do not print any blank lines.

Examples4

  1. Example 1

    Input
    1 0
    0 1
    4 3
    2 8
    3 27
    25 1000000000
    
    Expected output
    0
    0
    0
    2
    4
    20000000
    
  2. Example 2

    Input
    0 0
    
    Expected output
    0
    
  3. Example 3

    Input
    1 1
    
    Expected output
    0
    
  4. Example 4

    Input
    1 3
    
    Expected output
    1