Under construction

Still being built. Things may change

Old Book

Time limit1sMemory limit512 MB

Summary
Given that the first k pages are illustrations and the page numbers on text pages sum to s, find the minimum possible number of illustrations in the book.
Level

Hard8 of 10

Topics
Math, Number theory, Greedy, Binary search
Solved
No attempts yet

Problem

A group of young archaeologists is working at the excavation of an ancient library building. In the summer they found the remains of an old book and, after studying them, reached the following conclusions.

The book has several pages, and each page contains either text or an illustration. The first kk pages of the book definitely contain illustrations. All pages of the book are numbered, but the page number is written only on pages that contain text. The sum of the numbers of the pages with text is ss.

Unfortunately, neither the total number of pages in the book nor the number of illustrations could be determined. Still, the young archaeologists became interested in the smallest possible number of illustrations the book could have contained.

For example, if k=1k = 1 and s=8s = 8, the pages of the book could have the following contents ('T' denotes a page containing text, and 'I' denotes a page containing an illustration):

  • I T I I I T, pages 2 and 6 are numbered, 4 illustrations;
  • I I T I T, pages 3 and 5 are numbered, 3 illustrations;
  • I I I I I I I T, page 8 is numbered, 7 illustrations.

The minimum number of illustrations is 3.

Write a program that, given integers kk and ss, determines the smallest possible number of illustrations in the book.

Input

The first line of the input contains the integer kk (0≤k≤1090 \le k \le 10^9).

The second line of the input contains the integer ss (k+1≤s≤1012k + 1 \le s \le 10^{12}).

Output

Output a single integer: the minimum number of illustrations in the book.

Examples1

  1. Example 1

    Input
    1
    8
    
    Expected output
    3